Submission #995728

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<map>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int inf = 1000000007;

int n;
struct P {
    int x,y,id;
    P() {}
    P(int x,int y, int id):x(x),y(y),id(id) {}
    bool operator<(const P&a)const {
        return x==a.x?y<a.y:x<a.x;
    }
} p[maxn];

int main() {
   // freopen("in.cpp","r",stdin);
    cin>>n;
    for(int i=1; i<=n; i++) {
        int x,y;
        cin>>x>>y;
        p[i]=P(x,y,i);
    }
    if(p[1].y!=p[2].x||p[1].y>n-1||p[1].x!=0||p[2].y!=0)cout<<-1<<endl;
    else {
        if(n==2) {
            cout<<1<<endl;
        } else {
            sort(p+3,p+n);
            unordered_map<int,int>umap;
            bool fail = false;
            for(int i=3; i<=n; i++) {
                if(p[i].x+p[i].y==p[1].y&&p[i].x&&p[i].y) {
                    umap[p[i].x] = 1;
                }
                if((!p[i].x)||(!p[i].y))fail=true;
                if(p[i].x>p[i].y+p[1].y||p[i].y>p[i].x+p[1].y)fail=true;
                if(p[i].x+p[i].y<p[1].y)fail=true;
            }
            for(int i=1; i<p[1].y; i++)if(umap.find(i)==umap.end()) {
                    fail = true;
                    break;
                }
            int ret=0;
            umap.clear();
            umap[0]=1;
            for(int i=3; i<=n; i++) {
                if(p[i].y==p[i].x+p[1].y) {
                    if(umap.find(p[i].x-1)==umap.end()) {
                        fail=true;
                        break;
                    } else {
                        umap[p[i].x]=1;
                        ret++;
                    }
                }
            }
            umap.clear();
            umap[0]=1;
            for(int i=3; i<=n; i++) {
                if(p[i].x==p[i].y+p[1].y) {
                    if(umap.find(p[i].y-1)==umap.end()) {
                        fail=true;
                        break;
                    } else {
                        umap[p[i].y]=1;
                        ret++;
                    }
                }
            }
            umap.clear();
            for(int i=3; i<=n; i++) {
                if(p[i].x+p[i].y==p[1].y) {
                    if(umap.find(p[i].x)==umap.end()) {
                        umap[p[i].x]=1;
                    } else umap[p[i].x]++;
                }
            }
            umap[0] = 1;
            umap[p[1].y]=1;
            for(int i=0; i<p[1].y; i++) {
                if(umap.find(i)==umap.end()||umap.find(i+1)==umap.end()) {
                    fail = true;
                    break;
                }
                ret+=max(umap[i],umap[i+1]);
            }
            map<pair<int,int>,int>mp;
            for(int i=1; i<p[1].y; i++)mp[make_pair(i,p[1].y-i)] = 1;
            for(int i=3; i<=n; i++) {
                if(p[i].x+p[i].y==p[1].y)continue;
                if(p[i].x==p[i].y+p[1].y)continue;
                if(p[i].y==p[i].x+p[1].y)continue;
                if(mp[make_pair(p[i].x -1,p[i].y-1)]) {
                    ret++;
                    mp[make_pair(p[i].x,p[i].y)]=1;
                } else {
                    if(p[i].x+p[i].y==p[1].y+1) {
                        ret+=2;
                        mp[make_pair(p[i].x,p[i].y)]=1;
                    } else {
                        fail=true;
                        break;
                    }
                }
            }
            if(fail)cout<<-1<<endl;
            else cout<<ret<<endl;
        }
    }
    return 0;
}

Submission Info

Judge Result