Submission #1000423
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, int> l[210000]; // 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 | 1688 Byte |
Status | WA |
Exec Time | 364 ms |
Memory | 40052 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 | AC | 78 ms | 10880 KB |
01-02.txt | AC | 55 ms | 10880 KB |
01-03.txt | AC | 14 ms | 10112 KB |
01-04.txt | AC | 14 ms | 10112 KB |
01-05.txt | AC | 15 ms | 10112 KB |
01-06.txt | WA | 42 ms | 10496 KB |
01-07.txt | AC | 98 ms | 11392 KB |
01-08.txt | WA | 97 ms | 11392 KB |
01-09.txt | WA | 79 ms | 11008 KB |
01-10.txt | WA | 65 ms | 10880 KB |
01-11.txt | AC | 89 ms | 11136 KB |
01-12.txt | AC | 88 ms | 11136 KB |
01-13.txt | AC | 210 ms | 26112 KB |
01-14.txt | AC | 364 ms | 40052 KB |
01-15.txt | AC | 239 ms | 29568 KB |
01-16.txt | AC | 62 ms | 10880 KB |
01-17.txt | WA | 63 ms | 10880 KB |
01-18.txt | AC | 60 ms | 10880 KB |
01-19.txt | AC | 265 ms | 29952 KB |
01-20.txt | WA | 232 ms | 23808 KB |
01-21.txt | WA | 236 ms | 24064 KB |
01-22.txt | WA | 186 ms | 17792 KB |
01-23.txt | AC | 86 ms | 11392 KB |
01-24.txt | AC | 93 ms | 11392 KB |
01-25.txt | AC | 60 ms | 10880 KB |
01-26.txt | AC | 63 ms | 10880 KB |
01-27.txt | AC | 71 ms | 11264 KB |
01-28.txt | AC | 71 ms | 11392 KB |
01-29.txt | AC | 14 ms | 10112 KB |
01-30.txt | AC | 14 ms | 10112 KB |
01-31.txt | AC | 14 ms | 10112 KB |
sample-01.txt | AC | 14 ms | 10112 KB |
sample-02.txt | AC | 14 ms | 10112 KB |