Submission #1828032
Source Code Expand
#include<bits/stdc++.h> using namespace std; const int maxn=100005; struct SHIT { int one,two; bool operator<(const SHIT &b)const { if(this->one!=b.one) return (this->one<b.one); return (this->two<b.two); } }shit[maxn]; bool cmp(SHIT a,SHIT b) { if(a.one+a.two!=b.one+b.two) return a.one+a.two<b.one+b.two; return a.one<b.one; } map<SHIT,bool>mp; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&shit[i].one,&shit[i].two); } if(!(shit[1].one==shit[2].two&&shit[1].one==0&&shit[1].two!=0)){ puts("-1"); return 0; } int mn=shit[1].two; int ans=2*n-2; if(n==2){ if(mn==1){ puts("1"); } else{ puts("-1"); } return 0; } for(int i=3;i<=n;i++) { if(shit[i].one==0||shit[i].two==0||shit[i].one+shit[i].two<mn){ puts("-1"); return 0; } } sort(shit+1,shit+n+1,cmp); mp.clear(); for(int i=1,j;i<=n;i=j) { j=i+1; while(j<=n&&shit[j].one+shit[j].two==shit[i].one+shit[i].two) j++; for(int k=i;k<j;k++) mp[shit[k]]=1; int last=0,left=0; for(int k=i,tk;k<j;k=tk) { tk=k+1; while(tk<j&&shit[tk].one==shit[k].one&&shit[tk].two==shit[k].two){ tk++; } int now=tk-k; SHIT tmp1,tmp2; tmp1.one=shit[k].one-1; tmp1.two=shit[k].two-1; if(mp.count(tmp1)){ ans-=now; last=shit[i].one; left=now; continue; } tmp1.one=shit[k].one-1; tmp1.two=shit[k].two+1; tmp2.one=shit[k].one+1; tmp2.two=shit[k].two-1; bool one=0,two=0; one=one|mp.count(tmp1); two=two|mp.count(tmp2); tmp1.two--; tmp2.one--; one=one|mp.count(tmp1); two=two|mp.count(tmp2); if((one==0||two==0)&&shit[k].one!=0&&shit[k].two!=0){ //printf("%d k %d\n",shit[k].one,shit[k].two); puts("-1"); return 0; } if(last+1==shit[k].one){ ans-=max(now,left); } last=shit[i].one; left=now; } } printf("%d\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Distance Pairs |
User | munaiyi |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2577 Byte |
Status | WA |
Exec Time | 112 ms |
Memory | 7296 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:22:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:25:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&shit[i].one,&shit[i].two); ^
Judge Result
Set Name | sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1500 | ||||||||
Status |
|
|
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 | 17 ms | 1024 KB |
01-02.txt | AC | 14 ms | 1024 KB |
01-03.txt | AC | 1 ms | 256 KB |
01-04.txt | AC | 1 ms | 256 KB |
01-05.txt | WA | 2 ms | 256 KB |
01-06.txt | WA | 13 ms | 640 KB |
01-07.txt | WA | 30 ms | 1280 KB |
01-08.txt | WA | 30 ms | 1408 KB |
01-09.txt | WA | 26 ms | 1152 KB |
01-10.txt | WA | 23 ms | 1024 KB |
01-11.txt | WA | 28 ms | 1152 KB |
01-12.txt | WA | 27 ms | 1152 KB |
01-13.txt | WA | 69 ms | 7296 KB |
01-14.txt | WA | 112 ms | 7296 KB |
01-15.txt | AC | 72 ms | 7296 KB |
01-16.txt | WA | 19 ms | 1024 KB |
01-17.txt | WA | 19 ms | 1024 KB |
01-18.txt | WA | 19 ms | 1024 KB |
01-19.txt | WA | 77 ms | 7296 KB |
01-20.txt | WA | 65 ms | 6016 KB |
01-21.txt | WA | 66 ms | 6144 KB |
01-22.txt | WA | 48 ms | 3712 KB |
01-23.txt | AC | 25 ms | 1024 KB |
01-24.txt | AC | 29 ms | 1408 KB |
01-25.txt | AC | 15 ms | 1024 KB |
01-26.txt | AC | 15 ms | 1024 KB |
01-27.txt | AC | 15 ms | 1024 KB |
01-28.txt | AC | 15 ms | 1024 KB |
01-29.txt | AC | 1 ms | 256 KB |
01-30.txt | AC | 1 ms | 256 KB |
01-31.txt | WA | 1 ms | 256 KB |
sample-01.txt | WA | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |