Submission #1000028

---

Source Code Expand

#include <cstdio>
#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));
}

pair<int, int> before(pair<int, int> p, int c) {
    int m1, m2;
    
    if (check(p, -1, -1)) {
        m1 = c;
    } else if (check(p, -1, 0) && check(p, 0, -1)) {
        m1 = c * 2;
    } else {
        m1 = 1e9;
    }
    
    if (check(p, -1, 0)) {
        m2 = c;
    } else {
        m2 = 1e9;
    }
    
    return make_pair(m1, m2);
}

int solve() {
    int n, d, m = 0, 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;
            
            m = max(m, a + b);
        }
        
        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 <= m; i++) {
        pair <int, int> p;
        
        if (mp[i].size() == 0) continue;
        
        for (it = mp[i].begin(); it != mp[i].end(); it++) {
            if (it == mp[i].begin()) {
                p = before(it->first, it->second);
            } else {
                it2 = it;
                it2--;
                
                if (it2->first.first + 1 != it->first.first) {
                    if (p.first >= 1e9) return -1;
                    
                    ans += p.first;
                    p = before(it->first, it->second);
                } else {
                    int m1 = 1e9, m2 = 1e9, c = max(it->second, it2->second);
                    
                    if (check(it->first, -1, -1)) m1 = min(m1, min(p.first + it->second, p.second + c + it->second));
                    if (check(it->first, 0, -1)) m1 = min(m1, min(p.first + c + it->second, p.second + c + it->second));
                    if (check(it->first, -1, 0) && check(it->first, 0, -1)) m1 = min(m1, p.first + it->second * 2);
                    
                    m2 = min(m2, min(p.first + c, p.second + c));
                    if (check(it->first, -1, 0)) m2 = min(m2, p.second + it->second);
                    
                    p = make_pair(m1, m2);
                }
            }
        }
        
        if (p.first >= 1e9) return -1;
        ans += p.first;
    }
    
    return ans;
}

int main() {
    printf("%d\n", solve());
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int solve()’:
./Main.cpp:39:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:44: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