Submission #2166260
Source Code Expand
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}
const int N = 1e5 + 10;
int n , x[N] , y[N];
void check(bool ok) {
if(!ok) {
puts("-1");
exit(0);
}
}
int main(){
scanf("%d",&n);
rep(i,0,n) scanf("%d%d",x+i,y+i);
check(x[0] == 0 && y[1] == 0 && x[1] > 0 && x[1] == y[0]);
rep(i,2,n) check(x[i] > 0 && y[i] > 0);
map<pii,int> S;
rep(i,0,n) S[mp(x[i],y[i])]++;
rep(i,0,n) {
if(x[i]) check(S.count(mp(x[i]-1,y[i]-1))||S.count(mp(x[i]-1,y[i]))||S.count(mp(x[i]-1,y[i]+1)));
if(y[i]) check(S.count(mp(x[i]-1,y[i]-1))||S.count(mp(x[i],y[i]-1))||S.count(mp(x[i]+1,y[i]-1)));
}
int res = 2 * n - 2;
vector<pair<pii,int> > pts;
for(auto e : S) pts.pb(e);
sort(all(pts),[&](pair<pii,int> a,pair<pii,int> b){
int sa=a.fi.fi+a.fi.se;
int sb=b.fi.fi+b.fi.se;
if(sa!=sb) return sa < sb;
return a.fi.fi < b.fi.fi;
});
int remain = 0;
rep(i,0,n) {
int x , y , cnt;
tie(x , y) = pts[i].fi;
cnt = pts[i].se;
int match = min(remain , cnt);
res -= match;
if(S.count(mp(x - 1 , y - 1))) {
int link = cnt - match;
res -= link;
cnt -= link;
}
if(i + 1 < n && x + 1 == pts[i+1].fi.fi && y - 1 == pts[i+1].fi.se)
remain = cnt;
else
remain = 0;
}
printf("%d\n",res);
return 0;
}
Submission Info
Submission Time
2018-03-06 17:12:06+0900
Task
A - Distance Pairs
User
Y_UME
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2084 Byte
Status
RE
Exec Time
302 ms
Memory
8952 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:48:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:49:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i,0,n) scanf("%d%d",x+i,y+i);
^
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
49 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
2 ms
256 KB
01-06.txt
RE
302 ms
640 KB
01-07.txt
RE
140 ms
1408 KB
01-08.txt
RE
140 ms
1536 KB
01-09.txt
RE
127 ms
1152 KB
01-10.txt
RE
118 ms
1024 KB
01-11.txt
RE
134 ms
1280 KB
01-12.txt
RE
131 ms
1152 KB
01-13.txt
AC
112 ms
8952 KB
01-14.txt
AC
144 ms
8952 KB
01-15.txt
AC
107 ms
8952 KB
01-16.txt
RE
114 ms
1024 KB
01-17.txt
RE
116 ms
1024 KB
01-18.txt
RE
114 ms
1024 KB
01-19.txt
AC
131 ms
8952 KB
01-20.txt
AC
124 ms
7800 KB
01-21.txt
AC
128 ms
7800 KB
01-22.txt
RE
193 ms
4604 KB
01-23.txt
AC
33 ms
1408 KB
01-24.txt
AC
39 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
AC
1 ms
256 KB
sample-01.txt
AC
1 ms
256 KB
sample-02.txt
AC
1 ms
256 KB