제출 #1327798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1327798		lucasdmy	동굴 (IOI13_cave)	C++20	100 / 100	488 ms	504 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n){
    int state[n], resp[n];
    for(int k=0;k<n;k++){
        state[k]=-1;
        resp[k]=-1;
    }
    for(int k=0;k<n;k++){
        int p1=0, p2=n-1, my_state=0;
        int query[n];
        for(int i=0;i<n;i++){
            if(state[i]!=-1){
                query[i]=state[i];
            }else{
                query[i]=0;
            }
        }
        int aux=tryCombination(query);
        if(aux==k){
            my_state=1;
        }
        while(p1!=p2){
            int m=(p1+p2)/2;
            for(int i=0;i<n;i++){
                if(state[i]!=-1){
                    query[i]=state[i];
                }else if(p1<=i and i<=m){
                    query[i]=my_state;
                }else{
                    query[i]=(my_state+1)%2;
                }
            }
            if(tryCombination(query)==k){
                p1=m+1;
            }else{
                p2=m;
            }
        }
        state[p2]=my_state;
        resp[p2]=k;
    }
    answer(state, resp);
}

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