Submission #146433

#	Time	Username	Problem	Language	Result	Execution time	Memory
146433		achibasadzishvili	Cave (IOI13_cave)	C++14	100 / 100	557 ms	644 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll dor[50005],fix[40005],kon[40005],ans[40005];
ll ind,that,h,f,n;
int v[5000];
//tryCombination
void go(ll x,ll y){
    if(x == y){
        ans[ind] = x;
        return;
    }
    
    for(int i=x; i <= (x + y) / 2; i++)
        if(fix[i] != 1)
            v[i] ^= 1;
//    cout << ind << " " << x << " " << y << endl;
    int h = tryCombination(v);
//    cout << "Got " << h << endl;
    for(int i=x; i <= (x + y) / 2; i++)
        if(fix[i] != 1)
            v[i] ^= 1;
    if(h == -1){
        h = 5000;
    }
    for(int i=1; i<=n; i++){
        
    }
    if(h > ind){
        go(x , (x + y) / 2);
    }
    else {
        go((x + y) / 2 + 1 , y);
    }
}

void exploreCave(int n){
    for(int i=0; i<n; i++){
        ind = i;
        for(int j=0; j<n; j++)
            if(fix[j] == 0)
                v[j] = 0;
            else
                v[j] = kon[j];
        int f = tryCombination(v);
        if(f == -1)
            f = n;
        if(f > i){
            that = 0;
            for(int j=0; j<n; j++)
                if(fix[j] == 0)
                    v[j] = 1;
                else
                    v[j] = kon[j];
        }
        if(f == i)
            that = 1;
        go(0 , n - 1);
    //    cout << ans[ind] << " " << that << endl;
        fix[ans[i]] = 1;
        dor[ans[i]] = i;
        kon[ans[i]] = that;
    }
    
    int s[n],d[n];
    
    for(int i=0; i<n; i++)
        d[i] = kon[i];
    for(int i=0; i<n; i++)
        s[i] = dor[i];
    answer(d , s);
    
}

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