Submission #2274021

---

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, map<int, int>> s;
        for (int i = 0; i < n; i ++) {
                s[p[i].first + p[i].second][p[i].first] ++;
        }
        int matching = 0;
        for (auto mpmp : s) {
                auto sum = mpmp.first;
                auto mp = mpmp.second;
                vector<pair<int, int>> v;
                for (auto it : mp) {
                        v.emplace_back(it.first, it.second);
                }
                sort(v.begin(), v.end());
                vector<pair<bool, pair<int, int>>> t; //(bottom left exists, number of the same position)
                for (auto u : v) {
                        int a = u.first;
                        int b = sum - a;
                        bool ex = ps.count({a - 1, b - 1});
                        t.push_back({ex, {u.second, u.second}});
                }
                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

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