Submission #1000427
Source Code Expand
#include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; map<int, map<int,int> > d; //exists map<int, map<int,int> > l; // freq[sum][xval] vector<int> xval;// vector<int> freq; // int n; int a[210000], b[210000]; int main(){ cin >> n; for(int i = 0; i < n; i++) cin >> a[i] >> b[i]; if(a[0] != 0 || b[1] != 0 || a[1] != b[0] || a[1] == 0 || b[0] == 0){ cout << -1 << endl; return 0; } for(int i = 0; i < n; i++){ if(a[i] + b[i] < a[0] + b[0]){ cout << -1 << endl; return 0; } if(i >= 2 && (a[i] == 0 || b[i] == 0) ){ cout << -1 << endl; return 0; } d[a[i]][b[i]] = 1; l[a[i]+b[i]][a[i]]++; } for(int i = 0; i < n; i++){ if(a[i] > 0){ if(!d[a[i]-1][b[i]-1] && !d[a[i]-1][b[i]] && !d[a[i]-1][b[i]+1]){ cout << -1 << endl; return 0; } } if(b[i] > 0){ if(!d[a[i]-1][b[i]-1] && !d[a[i]][b[i]-1] && !d[a[i]+1][b[i]-1]){ cout << -1 << endl; return 0; } } } LL ans = 0; for(int i = 0; i < 210000; i++){ xval.clear(); freq.clear(); for(map<int, int>::iterator it = l[i].begin(); it != l[i].end(); it++){ xval.push_back(it->first); freq.push_back(it->second); } int l = 0; for(int j = 0; j < xval.size(); j++){ int numl = freq[j]; int numd = freq[j]; numl -= l; if(numl < 0) numl = 0; int xc = xval[j]; int yc = i-xval[j]; if(xc == 0) numl = 0; if(yc == 0) numd = 0; if(d[xc-1][yc-1]){ int r = min(numl,numd); numl -= r; numd -= r; ans += r; } ans += numl; l = numd; ans += numd; if(j + 1 == xval.size() || xval[j+1] != xval[j] + 1) l = 0; } } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Distance Pairs |
User | ksun48 |
Language | C++14 (GCC 5.4.1) |
Score | 1500 |
Code Size | 1717 Byte |
Status | AC |
Exec Time | 514 ms |
Memory | 49652 KB |
Judge Result
Set Name | sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1500 / 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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 67 ms | 1024 KB |
01-02.txt | AC | 44 ms | 1024 KB |
01-03.txt | AC | 129 ms | 19968 KB |
01-04.txt | AC | 131 ms | 19968 KB |
01-05.txt | AC | 128 ms | 19968 KB |
01-06.txt | AC | 153 ms | 20352 KB |
01-07.txt | AC | 210 ms | 21248 KB |
01-08.txt | AC | 206 ms | 21248 KB |
01-09.txt | AC | 203 ms | 20864 KB |
01-10.txt | AC | 180 ms | 20736 KB |
01-11.txt | AC | 211 ms | 20992 KB |
01-12.txt | AC | 205 ms | 20992 KB |
01-13.txt | AC | 336 ms | 35840 KB |
01-14.txt | AC | 514 ms | 49652 KB |
01-15.txt | AC | 336 ms | 39424 KB |
01-16.txt | AC | 171 ms | 20736 KB |
01-17.txt | AC | 170 ms | 20736 KB |
01-18.txt | AC | 173 ms | 20736 KB |
01-19.txt | AC | 394 ms | 39680 KB |
01-20.txt | AC | 364 ms | 33664 KB |
01-21.txt | AC | 354 ms | 33792 KB |
01-22.txt | AC | 301 ms | 27520 KB |
01-23.txt | AC | 80 ms | 1536 KB |
01-24.txt | AC | 88 ms | 1536 KB |
01-25.txt | AC | 49 ms | 1024 KB |
01-26.txt | AC | 50 ms | 1024 KB |
01-27.txt | AC | 62 ms | 1408 KB |
01-28.txt | AC | 61 ms | 1536 KB |
01-29.txt | AC | 3 ms | 256 KB |
01-30.txt | AC | 3 ms | 256 KB |
01-31.txt | AC | 3 ms | 256 KB |
sample-01.txt | AC | 129 ms | 19968 KB |
sample-02.txt | AC | 3 ms | 256 KB |