Submission #1830737
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; mp.clear(); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&shit[i].one,&shit[i].two); mp[shit[i]]=1; } if(!(shit[1].one==shit[2].two&&shit[1].two==shit[2].one&&shit[1].one==0&&shit[1].two!=0)){ puts("-1"); return 0; } int mn=shit[1].two; int ans=2*n-2; 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); 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){ tk++; } int now=tk-k; bool one=0,two=0; SHIT tmp1,tmp2; tmp1.one=shit[k].one-1; tmp1.two=shit[k].two-1; if(mp.count(tmp1)){ int del=min(now,left); ans-=del; ans-=now-left; now=del; if(last+1!=shit[k].one) now=0; last=shit[k].one; left=now; continue; one=1;two=1; } tmp1.one=shit[k].one-1; tmp1.two=shit[k].two+1; tmp2.one=shit[k].one+1; tmp2.two=shit[k].two-1; 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(shit[k].one==0)one=1; if(shit[k].two==0) two=1; if(one==0||two==0){ puts("-1"); return 0; } int del=0; if(last+1==shit[k].one){ del=min(now,left); ans-=del; } tmp1.two--; last=shit[k].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 | 2714 Byte |
Status | WA |
Exec Time | 96 ms |
Memory | 7296 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:23:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:26: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 | 53 ms | 7296 KB |
01-02.txt | AC | 18 ms | 1024 KB |
01-03.txt | AC | 1 ms | 256 KB |
01-04.txt | AC | 1 ms | 256 KB |
01-05.txt | AC | 1 ms | 256 KB |
01-06.txt | AC | 14 ms | 640 KB |
01-07.txt | AC | 38 ms | 1280 KB |
01-08.txt | WA | 39 ms | 1408 KB |
01-09.txt | WA | 31 ms | 1152 KB |
01-10.txt | AC | 25 ms | 1024 KB |
01-11.txt | AC | 34 ms | 1152 KB |
01-12.txt | AC | 32 ms | 1152 KB |
01-13.txt | AC | 83 ms | 7296 KB |
01-14.txt | AC | 96 ms | 7296 KB |
01-15.txt | AC | 76 ms | 7296 KB |
01-16.txt | AC | 20 ms | 1024 KB |
01-17.txt | AC | 19 ms | 1024 KB |
01-18.txt | AC | 20 ms | 1024 KB |
01-19.txt | AC | 92 ms | 7296 KB |
01-20.txt | WA | 91 ms | 6016 KB |
01-21.txt | WA | 92 ms | 6144 KB |
01-22.txt | WA | 68 ms | 3712 KB |
01-23.txt | AC | 35 ms | 1408 KB |
01-24.txt | AC | 39 ms | 1408 KB |
01-25.txt | AC | 24 ms | 1280 KB |
01-26.txt | AC | 24 ms | 1280 KB |
01-27.txt | AC | 24 ms | 1280 KB |
01-28.txt | AC | 25 ms | 1408 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 |