Submission #764652

#	Time	Username	Problem	Language	Result	Execution time	Memory
764652		lalig777	Cave (IOI13_cave)	C++14	12 / 100	142 ms	444 KiB

cave

#include "cave.h"
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N;
/*int tryCombination(int S[]){
    for (int i=0; i<N; i++) cout<<S[i]<<" ";
    cout<<endl;
    int a;
    cin>>a;
    return a;
}
void answer(int S[], int D[]){
    for (int i=0; i<N; i++) cout<<S[i]<<" ";
    cout<<endl;
    for (int i=0; i<N; i++) cout<<D[i]<<" ";
    cout<<endl;
    return;
}*/

void exploreCave(int N) {
    int S[N]={0};
    int ans[N];
    memset(ans, -1, sizeof ans);
    int D[N]={0};
    for (int i=0; i<N; i++){
        int l=0, r=N-1, m, u;
        for (int j=0; j<N; j++){
            if (ans[j]!=-1) S[j]=ans[j];
            else S[j]=0;
        }
        int res=tryCombination(S);
        m = l + (r-l)/2;
        for (int j=0; j<=m; j++){
            if (ans[j]!=-1) S[j]=ans[j];
            else S[j]=1;
        }
        int res2=tryCombination(S);
        if (res2==res and res==i) {
            u=1;
            l=m+1;
        } else if (res2==res and res!=i) {
            u=0;
            l=m+1;
        } else if (res2!=res and res==i){
            u=1;
            r=m;
        } else{
            u=0;
            r=m;
        }
        /*cout << "pre binary search\n";
        cout << "ans";
        for (int k: ans) cout << ' ' << k;
        cout << '\n';
        cout << "S";
        for (int k: S) cout << ' ' << k;
        cout << '\n';
        cout << "i " << i << endl;*/
        while(l<=r){
            m = l + (r-l)/2;
            if (l==r) {
                D[l]=i;
                ans[l]=u;
                /*cout << l << ' ' << r << '\n';
                cout << "i " << i << endl;
                cout << "ans";
                for (int k: ans) cout << ' ' << k;
                cout << '\n';
                cout << "D";
                for (int k: D) cout << ' ' << k;
                cout << '\n';*/
                break;
            }
            for (int j=l; j<=m; j++){
                if (ans[j]!=-1) S[j]=ans[j];
                else S[j]=u;
            }for (int j=m+1; j<=r; j++){
                if (ans[j]!=-1) S[j]=ans[j];
                else S[j]= 1-u;
            }
            res=tryCombination(S);
            if (res==i) l=m+1;
            else r=m;
            /*cout << "i " << i << endl;
            cout << l << ' ' << r << '\n';
            cout << "ans";
            for (int k: ans) cout << ' ' << k;
            cout << '\n';
            cout << "S";
            for (int k: S) cout << ' ' << k;
            cout << '\n';*/
        }
    }answer(ans, D);
}
/*int main(){
    cin>>N;
    exploreCave(N);
    return 0;
}*/

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