Submission #218296

#	Time	Username	Problem	Language	Result	Execution time	Memory
218296		summitwei	Cave (IOI13_cave)	C++17	100 / 100	657 ms	764 KiB

cave

#include <bits/stdc++.h>
#include <cave.h>
using namespace std;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
#define INF 0x3f3f3f3f
#define MOD 1000000007LL
#define EPSILON 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair

#define FOR(i, a, b) for (ll i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (ll i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (ll i=(a); i >= b; i--)

#define MN 5005
int n;
/*int tryCombination(int S[]){
    F0R(i, n){
        cout << S[i] << " ";
    }
    cout << endl;
    cout.flush();
    int resp;
    cin >> resp;
    return resp;
}
void answer(int S[], int D[]){
    F0R(i, n){
        cout << S[i] << " ";
    }
    cout << "\n";
    F0R(i, n){
        cout << D[i] << " ";
    }
    cout << "\n";
    cout.flush();
    exit(0);
}*/
int vals[MN];
int conn[MN];
vi rel;
void assi(int x, int amt){
    FOR(i, 0, amt){
        vals[rel[i]] = x;
    }
    FOR(i, amt+1, rel.size()-1){
        vals[rel[i]] = 1-x;
    }
}
void exploreCave(int N){
    n = N;
    F0R(i, n) rel.pb(i);

    F0R(i, n){
        //for(auto u : rel) vals[u] = 0;

        int x;
        assi(0, rel.size()-1);
        if(tryCombination(vals) == i) x = 1;
        else x = 0;

        int l=-1, r=rel.size()-1;
        while(l+1<r){
            int mid = (l+r)/2;
            assi(x, mid);
            if(tryCombination(vals) == i){
                l = mid;
            } else{
                r = mid;
            }
        }
        vals[rel[r]] = x;
        conn[rel[r]] = i;
        rel.erase(rel.begin()+r);
    }
    answer(vals, conn);
}

/*int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);

    exploreCave(4);
    
    return 0;
}*/

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