Submission #223145

#	Time	Username	Problem	Language	Result	Execution time	Memory
223145		aggu_01000101	Cave (IOI13_cave)	C++14	100 / 100	393 ms	640 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#define mid(l, u) ((l+u)/2)
#define test(a) tryCombination(a);
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
int N;
/*int tryCombination(int a[]){
    cout<<"COMBINATION"<<endl;
    for(int i = 0;i<N;i++) cout<<a[i]<<" ";
    cout<<endl;
    int tr;
    cin>>tr;
    return tr;
}
void answer(int s[], int d[]){
    cout<<"ANSWER"<<endl;
    for(int i = 0;i<N;i++) cout<<s[i]<<" ";
    cout<<endl;
    for(int i = 0;i<N;i++) cout<<d[i]<<" ";
    cout<<endl;
}*/
void exploreCave(int n){
    N = n;
    int currdoor = 0;
    bool change[n];
    for(int i = 0;i<n;i++) change[i] = true;
    int q[n];
    int r;
    int ans[n];
    while(currdoor<n){
        for(int i = 0;i<n;i++){
            if(change[i]) q[i] = 1;
        }//
        r = test(q);
        int req = (r==currdoor);
        int l = 0;
        int u = n-1;
        while(l<u){
            int m = mid(l, u);
            for(int i = l;i<=m;i++){
                if(change[i]) q[i] = req;
            }
            for(int i = m+1;i<=u;i++){
                if(change[i]) q[i] = req^1;
            }
            r = test(q);
            if(r==currdoor){
                u = m;
            }
            else{
                l = m+1;
            }
        }
        change[l] = false;
        q[l] = (req^1);
        ans[l] = currdoor;
        currdoor++;
    }
    answer(q, ans);
}

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