Submission #435688

#	Time	Username	Problem	Language	Result	Execution time	Memory
435688		Odavey	Cave (IOI13_cave)	C++14	63 / 100	2090 ms	708 KiB

cave

//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#include "cave.h"
#define MX_N            5001
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

//int p[MX_N];
//int o[MX_N];

int tryCombination(int S[]);

//int tryCombination(vector<int> S){
//    int n = S.size();
//    cout << "Trying this combination\n";
//    for(int i=0;i<n;++i){
//        cout << S[i] << ' ';
//    }
//    cout << endl;
//    bool door[n];
//    for(int i=0;i<n;++i){
//        door[p[i]] = (S[i] == o[p[i]]);
//    }
//    for(int i=0;i<n;++i){
//        if(!door[i]){
//            cout << "It reaches all the way up to door " << i << "!\n";
//            return i;
//        }
//    }
//    cout << "It reaches all the way through!\n";
//    return -1;
//}

void answer (int S[], int D[]);

//void answer (vector<int> S, vector<int> D){
//    int n = S.size();
//    for(int i=0;i<n;++i){
//        cout << S[i] << " & " << D[i] << endl;
//    }
//    for(int i=0;i<n;++i){
//        if(!(S[i] == o[D[i]] && D[i] == p[i])){
//            cout << "WA\n";
//            return;
//        }
//    }
//    cout << "AC\n";
//    return;
//}

void exploreCave(int N){
    map<int, int> k;//lever i -> door j
    set<int> dk;//lever i
    int pos[N];//correct orientation of lever i
    memset(pos, -1, sizeof(pos));
    for(int i=0;i<N;++i){
        dk.insert(i);
    }
    for(int root=0;root<N;++root){
        int S[N];
        //vector<int> S(N);
        for(int x : dk){
            S[x] = 1;
        }
        for(auto it=k.begin();it!=k.end();++it){
            S[it->first] = pos[it->first];
        }
        int res = tryCombination(S);
        bool O = (res > root || res == -1);
        int lo=0, hi=(int)dk.size()-1;
        while(lo < hi){
            int mid = (lo+hi) >> 1;
            int cnt = 0;
            for(int x : dk){
                if(cnt <= mid){
                    S[x] = O;
                }else{
                    S[x] = !O;
                }
                ++cnt;
            }
            res = tryCombination(S);
            if(res > root || res == -1){
                hi = mid;
            }else{
                lo = mid+1;
            }
        }
        int cnt = 0;
        for(int x : dk){
            if(cnt == lo){
                k[x] = root;
                pos[x] = O;
                dk.erase(x);
//                cout << "Filled in the door at " << root << ", the switch is " << x << " and the orientation is " << O << endl;
                break;
            }
            ++cnt;
        }
    }
//    vector<int> S(N), D(N);
    int S[N];
    int D[N];
    for(int i=0;i<N;++i){
        S[i] = pos[i];
        D[i] = k[i];
    }
    answer(S, D);
    return;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 0 / 24