Submission #995868


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;
            unordered_map<int,int>umapx,umapy;
            mp[make_pair(0,p[1].y)]=1;
            mp[make_pair(p[1].y,0)]=1;
            umapx[0]=umapx[p[1].y]=1;
            umapy[0]=umapy[p[1].y]=1;
            for(int i=1; i<p[1].y; i++) {
                mp[make_pair(i,p[1].y-i)] = 1;
                umapx[i]=1;
                umapy[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++;
                    umapx[p[i].x]=1;
                    umapy[p[i].y]=1;
                    mp[make_pair(p[i].x,p[i].y)]=1;
                } else {
                    //cout<<p[i].x<<" "<<p[i].y<<endl;
                    if(umapx.find(p[i].x-1)!=umapx.end()&&umapy.find(p[i].y-1)!=umapy.end()) {
                        ret+=2;
                        mp[make_pair(p[i].x,p[i].y)]=1;
                        umapx[p[i].x]=1;
                        umapy[p[i].y]=1;
                    } else {
                        fail=true;
                        break;
                    }
                }
            }
            if(fail)cout<<-1<<endl;
            else cout<<ret<<endl;
        }
    }
    return 0;
}

Submission Info

Submission Time
Task A - Distance Pairs
User suiyuan2009
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4277 Byte
Status WA
Exec Time 147 ms
Memory 20004 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 1500
Status
AC × 1
WA × 1
AC × 18
WA × 15
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
Case Name Status Exec Time Memory
01-01.txt AC 122 ms 14792 KB
01-02.txt AC 42 ms 1408 KB
01-03.txt AC 3 ms 256 KB
01-04.txt AC 3 ms 256 KB
01-05.txt AC 3 ms 256 KB
01-06.txt WA 27 ms 896 KB
01-07.txt WA 61 ms 1792 KB
01-08.txt WA 58 ms 1792 KB
01-09.txt WA 54 ms 1536 KB
01-10.txt WA 48 ms 1408 KB
01-11.txt AC 59 ms 1664 KB
01-12.txt AC 59 ms 1536 KB
01-13.txt WA 77 ms 3468 KB
01-14.txt AC 147 ms 20004 KB
01-15.txt WA 69 ms 2304 KB
01-16.txt AC 41 ms 1408 KB
01-17.txt AC 40 ms 1408 KB
01-18.txt AC 43 ms 1408 KB
01-19.txt WA 87 ms 6016 KB
01-20.txt WA 106 ms 10880 KB
01-21.txt WA 108 ms 11008 KB
01-22.txt WA 89 ms 6400 KB
01-23.txt WA 58 ms 1792 KB
01-24.txt WA 57 ms 1792 KB
01-25.txt AC 40 ms 1408 KB
01-26.txt AC 41 ms 1408 KB
01-27.txt AC 57 ms 1664 KB
01-28.txt AC 58 ms 1792 KB
01-29.txt WA 3 ms 256 KB
01-30.txt AC 3 ms 256 KB
01-31.txt AC 3 ms 256 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt WA 3 ms 256 KB