Submission #1828629
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[k].one;
left=min(now,left);
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-=min(now,left);
}
last=shit[k].one;
left=now;
}
//printf("%d %d\n",shit[i].one+shit[i].two,ans);
}
printf("%d\n",ans);
return 0;
}
Submission Info
Submission Time
2017-12-03 21:37:12+0900
Task
A - Distance Pairs
User
munaiyi
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2645 Byte
Status
WA
Exec Time
138 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
AC
2 ms
256 KB
01-06.txt
AC
13 ms
640 KB
01-07.txt
AC
29 ms
1280 KB
01-08.txt
WA
29 ms
1408 KB
01-09.txt
AC
26 ms
1152 KB
01-10.txt
AC
22 ms
1024 KB
01-11.txt
AC
28 ms
1152 KB
01-12.txt
AC
27 ms
1152 KB
01-13.txt
AC
81 ms
7296 KB
01-14.txt
AC
138 ms
7296 KB
01-15.txt
AC
90 ms
7296 KB
01-16.txt
AC
19 ms
1024 KB
01-17.txt
AC
19 ms
1024 KB
01-18.txt
AC
19 ms
1024 KB
01-19.txt
AC
85 ms
7296 KB
01-20.txt
WA
68 ms
6016 KB
01-21.txt
WA
72 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
AC
1 ms
256 KB
sample-02.txt
AC
1 ms
256 KB