Submission #2273896


Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

void ng() {
        printf("-1\n");
        exit(0);
}

int main() {
        int n;
        scanf("%d", &n);
        set<pair<int, int>> ps;
        vector<pair<int, int>> p;
        for (int i = 0; i < n; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                p.emplace_back(a, b);
                ps.insert({a, b});
        }
        if (p[0].first != 0 || p[1].second != 0) ng();
        if (p[0].second != p[1].first) ng();
        if (p[0].second == 0) ng();
        for (int i = 2; i < n; i ++) {
                int a, b;
                tie(a, b) = p[i];
                if (a == 0 || b == 0) ng();
                if (!ps.count({a - 1, b + 1}) && !ps.count({a - 1, b}) && !ps.count({a - 1, b - 1})) ng();
                if (!ps.count({a + 1, b - 1}) && !ps.count({a, b - 1}) && !ps.count({a - 1, b - 1})) ng();
        }
        map<int, vector<pair<int, int>>> s;
        for (int i = 0; i < n; i ++) {
                s[p[i].first + p[i].second].emplace_back(p[i].first, p[i].second);
        }
        int matching = 0;
        for (auto mp : s) {
                vector<pair<int, int>> v = mp.second;
                sort(v.begin(), v.end());
                vector<pair<bool, pair<int, int>>> t; //(bottom left exists, number of the same position)
                int cur = v[0].first;
                int curi = 0;
                while (curi < (int) v.size()) {
                        int cnt = 0;
                        bool ex = ps.count({v[curi].first - 1, v[curi].second - 1});
                        while (curi < (int) v.size() && cur == v[curi].first) {
                                curi ++;
                                cnt ++;
                        }
                        t.push_back({ex, {cnt, cnt}});
                        cur = v[curi].first;
                }
                for (int i = 0; i < (int) t.size(); i ++) {
                        if (t[i].first) {
                                int d = min(t[i].second.first, t[i].second.second);
                                matching += d;
                                t[i].second.first -= d;
                                t[i].second.second -= d;
                        }
                        if (t[i].second.second > 0 && i + 1 < (int) t.size()) {
                                int d = min(t[i].second.second, t[i + 1].second.first);
                                matching += d;
                                t[i + 1].second.first -= d;
                        }
                }
        }
        printf("%d\n", 2 * n - 2 - matching);
        return 0;
}

Submission Info

Submission Time
Task A - Distance Pairs
User KokiYmgch
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2888 Byte
Status WA
Exec Time 202 ms
Memory 16628 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:20:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &n);
                        ^
./Main.cpp:25:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d", &a, &b);
                                      ^

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 1500
Status
AC × 2
AC × 31
WA × 4
Set Name Test Cases
sample sample-01.txt, sample-02.txt
All sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 48 ms 5748 KB
01-02.txt AC 18 ms 1408 KB
01-03.txt AC 1 ms 256 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 2 ms 256 KB
01-06.txt AC 15 ms 1528 KB
01-07.txt AC 73 ms 2388 KB
01-08.txt WA 57 ms 2420 KB
01-09.txt AC 36 ms 2328 KB
01-10.txt AC 27 ms 2676 KB
01-11.txt AC 69 ms 2352 KB
01-12.txt AC 64 ms 2344 KB
01-13.txt AC 189 ms 11508 KB
01-14.txt AC 105 ms 10356 KB
01-15.txt AC 202 ms 16628 KB
01-16.txt AC 23 ms 3444 KB
01-17.txt AC 20 ms 3444 KB
01-18.txt AC 21 ms 3444 KB
01-19.txt AC 146 ms 9972 KB
01-20.txt WA 107 ms 6900 KB
01-21.txt WA 111 ms 7028 KB
01-22.txt WA 85 ms 5364 KB
01-23.txt AC 35 ms 1528 KB
01-24.txt AC 46 ms 1528 KB
01-25.txt AC 24 ms 1492 KB
01-26.txt AC 24 ms 1492 KB
01-27.txt AC 37 ms 1492 KB
01-28.txt AC 36 ms 1528 KB
01-29.txt AC 1 ms 256 KB
01-30.txt AC 1 ms 256 KB
01-31.txt AC 1 ms 256 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB