Submission #1000426
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; 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 | 0 |
Code Size | 1700 Byte |
Status | WA |
Exec Time | 533 ms |
Memory | 62464 KB |
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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | WA | 533 ms | 62464 KB |
01-02.txt | WA | 197 ms | 20736 KB |
01-03.txt | AC | 143 ms | 19968 KB |
01-04.txt | AC | 139 ms | 19968 KB |
01-05.txt | AC | 141 ms | 19968 KB |
01-06.txt | WA | 163 ms | 20352 KB |
01-07.txt | AC | 227 ms | 21248 KB |
01-08.txt | WA | 227 ms | 21248 KB |
01-09.txt | WA | 206 ms | 20864 KB |
01-10.txt | WA | 193 ms | 20736 KB |
01-11.txt | AC | 226 ms | 20992 KB |
01-12.txt | AC | 221 ms | 20992 KB |
01-13.txt | AC | 337 ms | 35840 KB |
01-14.txt | AC | 477 ms | 49652 KB |
01-15.txt | AC | 307 ms | 39424 KB |
01-16.txt | AC | 201 ms | 20736 KB |
01-17.txt | WA | 183 ms | 20736 KB |
01-18.txt | AC | 183 ms | 20736 KB |
01-19.txt | AC | 386 ms | 39680 KB |
01-20.txt | WA | 373 ms | 33664 KB |
01-21.txt | WA | 372 ms | 33792 KB |
01-22.txt | WA | 314 ms | 27520 KB |
01-23.txt | WA | 228 ms | 21248 KB |
01-24.txt | WA | 227 ms | 21248 KB |
01-25.txt | WA | 226 ms | 21120 KB |
01-26.txt | WA | 227 ms | 21120 KB |
01-27.txt | WA | 223 ms | 21120 KB |
01-28.txt | WA | 230 ms | 21248 KB |
01-29.txt | WA | 143 ms | 19968 KB |
01-30.txt | WA | 135 ms | 19968 KB |
01-31.txt | WA | 132 ms | 19968 KB |
sample-01.txt | AC | 142 ms | 19968 KB |
sample-02.txt | WA | 143 ms | 19968 KB |