Submission #1004790


Source Code Expand

#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <tuple>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <complex>
#include <bitset>
#include <numeric>
#include <random>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n) ;++(i))
#define REPN(i,a,n) FOR((i),(a),(a)+(n))
#define FOR(i,a,b) for(int (i)=(a); (i)<(b) ;++(i))
#define PB push_back
#define MP make_pair
#define SE second
#define FI first
#define DBG(a) cerr<<(a)<<endl;
#define ALL(v) (v).begin(),(v).end()
typedef long long LL;  typedef pair<LL, LL> PLL; typedef vector<LL> VLL;
const LL LINF=334ll<<53; const int INF=15<<26; const LL MOD=1E9+7;
bool comp (pair<int,int> a, pair<int,int>b){
    return a.FI+a.SE<b.FI+b.SE or (a.FI+a.SE==b.FI+b.SE and a.FI<b.FI);
}
int cnt(multiset<pair<int,int>> &s, int a, int b){
    return s.count(make_pair(a,b));
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,dmax=0;
    cin >> n;
    vector<pair<int,int>> d;
    multiset<pair<int,int>> s;
    REP(i,n){
        int a,b;
        cin >> a>>b;
        //dmax=max(dmax,a+b);
        s.insert(make_pair(a,b));
        d.push_back(make_pair(a,b));
    }
    if(d[0].FI!=0 or d[1].SE!=0 or d[1].FI!=d[0].SE or d[0].SE==0){
        cout << -1 << endl; return 0;
    }
    FOR(i,2,n){
        if(d[i].FI==0 or d[i].SE==0){
            cout << -1 << endl; return 0;
        }
    }
    FOR(i,1,d[0].SE){
        if(cnt(s,i,d[0].SE-i)==0){
            cout << -1 << endl; return 0;
        }
    }
    //0~1
    int ans=cnt(s,1,d[0].SE-1);

    FOR(i,1,d[0].SE){
        ans+=max(cnt(s,i,d[0].SE-i),cnt(s,i+1,d[0].SE-i-1));
    }
    sort(d.begin(),d.end());
    d.erase(unique(ALL(d)),d.end());
    sort(d.begin(),d.end(),comp);
    int succ=0;
    for(auto it=lower_bound(ALL(d),make_pair(1,d[0].SE),comp); it<d.end();it++){
        int d0=it->FI,d1=it->SE,add=0;
        //DBG(ans)
        //cout << d0 << ' ' <<d1  <<' '<<succ<<endl;
        if(succ){
            add=succ;
            if(cnt(s,d0-1,d1-1)){
                add=cnt(s,d0,d1);
            }else if(cnt(s,d0+1,d1-1)){
                add=succ=cnt(s,d0,d1);
            }else if(cnt(s,d0,d1-1)){
                add=cnt(s,d0,d1)*2;
                succ=0;
            }else {
                cout << -1 << endl; return 0;
            }
        }else if(cnt(s,d0-1,d1-1)){
            add=cnt(s,d0,d1);
        }else if(cnt(s,d0-1,d1)or cnt(s,d0-1,d1+1)){
            add=cnt(s,d0,d1);
            if(cnt(s,d0+1,d1-1)){
                succ=add;
            }else if(cnt(s,d0,d1-1)){
                add*=2;
            }else{
                cout << -1 << endl; return 0;
            }
        }else{
            cout << -1 << endl; return 0;
        }
        ans+=add;
    }

    cout << ans <<endl;
    return 0;
}

Submission Info

Submission Time
Task A - Distance Pairs
User Hoi_koro
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3164 Byte
Status WA
Exec Time 95 ms
Memory 5748 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 1500
Status
AC × 2
AC × 23
WA × 10
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 52 ms 5748 KB
01-02.txt AC 51 ms 5748 KB
01-03.txt AC 2 ms 256 KB
01-04.txt AC 2 ms 256 KB
01-05.txt AC 3 ms 256 KB
01-06.txt WA 25 ms 3448 KB
01-07.txt WA 67 ms 5748 KB
01-08.txt WA 68 ms 5748 KB
01-09.txt WA 61 ms 5748 KB
01-10.txt WA 46 ms 5748 KB
01-11.txt AC 64 ms 5620 KB
01-12.txt AC 63 ms 5748 KB
01-13.txt AC 87 ms 5748 KB
01-14.txt AC 87 ms 5748 KB
01-15.txt AC 80 ms 5748 KB
01-16.txt AC 38 ms 5748 KB
01-17.txt AC 42 ms 5748 KB
01-18.txt AC 39 ms 5748 KB
01-19.txt WA 93 ms 5748 KB
01-20.txt WA 93 ms 5620 KB
01-21.txt WA 95 ms 5748 KB
01-22.txt WA 83 ms 5748 KB
01-23.txt AC 61 ms 5748 KB
01-24.txt WA 67 ms 5748 KB
01-25.txt AC 52 ms 5748 KB
01-26.txt AC 52 ms 5748 KB
01-27.txt AC 52 ms 5748 KB
01-28.txt AC 52 ms 5748 KB
01-29.txt AC 2 ms 256 KB
01-30.txt AC 2 ms 256 KB
01-31.txt AC 2 ms 256 KB
sample-01.txt AC 2 ms 256 KB
sample-02.txt AC 2 ms 256 KB