Submission #1000284


Source Code Expand

#include <cstdio>
#include <vector>
#include <map>
 
using namespace std;
 
map <pair<int, int>, int> mp[200000];
 
bool check(pair<int, int> p, int da, int db) {
    int a = p.first + da;
    int b = p.second + db;
    
    return mp[a + b].count(make_pair(a, b));
}

bool before(pair<int, int> p) {
    return check(p, -1, -1) || check(p, -1, 0);
}

bool after(pair<int, int> p) {
    return check(p, -1, -1) || check(p, 0, -1);
}

int calc(vector <pair<bool, int> >& v) {
    int ans = 0, c = 0, i;
    
    for (i = 0; i < v.size(); i++) {
        ans += v[i].second;
        
        if (v[i].first) {
            c = min(c, v[i].second);
        } else {
            if (v[i].second > c) ans += v[i].second - c;
            c = v[i].second;
        }
    }
    
    return ans;
}
 
int solve() {
    int n, d, ans = 0, i;
    map <pair<int, int>, int>::iterator it, it2;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        int a, b;
        
        scanf("%d %d", &a, &b);
        
        if (i == 0) {
            if (a != 0 || b == 0) return -1;
            
            d = b;
        } else if (i == 1) {
            if (a != d || b != 0) return -1;
        } else {
            if (a == 0 || b == 0 || a + b < d) return -1;
        }
        
        mp[a + b][make_pair(a, b)]++;
    }
    
    for (it = mp[d].begin(); it != mp[d].end(); it++) {
        if (it == mp[d].begin()) continue;
        
        it2 = it;
        it2--;
        
        if (it2->first.first + 1 != it->first.first) return -1;
        
        ans += max(it->second, it2->second);
    }
    
    for (i = d + 1; i < n * 2; i++) {
        vector <pair<bool, int> > v;
        
        if (mp[i].size() == 0) continue;
        
        for (it = mp[i].begin(); it != mp[i].end(); it++) {
            if (it == mp[i].begin()) {
                if (!before(it->first)) return -1;
                
                v.push_back(make_pair(check(it->first, -1, -1), it->second));
            } else {
                it2 = it;
                it2--;
                
                if (it2->first.first + 1 != it->first.first) {
                    if (!after(it2->first) || !before(it->first)) return -1;
                    
                    ans += calc(v);
                    v.clear();
                }
                
                v.push_back(make_pair(check(it->first, -1, -1), it->second));
            }
        }
        
        it--;
        if (!after(it->first)) return -1;
        
        ans += calc(v);
    }
    
    return ans;
}
 
int main() {
    printf("%d\n", solve());
    
    return 0;
}

Submission Info

Submission Time
Task A - Distance Pairs
User kawatea
Language C++14 (GCC 5.4.1)
Score 1500
Code Size 2736 Byte
Status AC
Exec Time 75 ms
Memory 16256 KB

Compile Error

./Main.cpp: In function ‘int solve()’:
./Main.cpp:45:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:50:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
                               ^

Judge Result

Set Name sample All
Score / Max Score 0 / 0 1500 / 1500
Status
AC × 2
AC × 33
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 12 ms 9600 KB
01-02.txt AC 12 ms 9600 KB
01-03.txt AC 12 ms 9600 KB
01-04.txt AC 12 ms 9600 KB
01-05.txt AC 13 ms 9600 KB
01-06.txt AC 21 ms 9600 KB
01-07.txt AC 33 ms 9856 KB
01-08.txt AC 34 ms 9984 KB
01-09.txt AC 29 ms 9728 KB
01-10.txt AC 28 ms 9600 KB
01-11.txt AC 31 ms 9856 KB
01-12.txt AC 30 ms 9728 KB
01-13.txt AC 60 ms 15872 KB
01-14.txt AC 73 ms 15872 KB
01-15.txt AC 58 ms 15872 KB
01-16.txt AC 26 ms 9600 KB
01-17.txt AC 26 ms 9600 KB
01-18.txt AC 26 ms 9600 KB
01-19.txt AC 72 ms 16256 KB
01-20.txt AC 74 ms 14976 KB
01-21.txt AC 75 ms 15104 KB
01-22.txt AC 58 ms 12544 KB
01-23.txt AC 33 ms 9984 KB
01-24.txt AC 33 ms 9984 KB
01-25.txt AC 12 ms 9600 KB
01-26.txt AC 12 ms 9600 KB
01-27.txt AC 23 ms 9856 KB
01-28.txt AC 22 ms 9856 KB
01-29.txt AC 12 ms 9600 KB
01-30.txt AC 12 ms 9600 KB
01-31.txt AC 12 ms 9728 KB
sample-01.txt AC 12 ms 9600 KB
sample-02.txt AC 12 ms 9600 KB