제출 #962644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
962644		hirayuu_oj	동굴 (IOI13_cave)	C++17	0 / 100	452 ms	544 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=1LL<<60;

void exploreCave(int N) {
    int s[N];
    rep(i,N){
        s[i]=-1;
    }
    int ques[N];
    int d[N];
    rep(i,N){
        int door,right;
        rep(j,N){
            if(s[j]==-1)ques[j]=0;
            else ques[j]=s[j];
        }
        door=tryCombination(ques);
        if(door==i)right=1;
        else right=0;
        int ok=0,ng=N-i;
        while(ng-ok>1){
            int mid=(ok+ng)/2;
            int cnt=0;
            rep(j,N){
                if(s[j]==-1){
                    if(mid<=cnt && cnt<ng){
                        ques[j]=right;
                    }
                    else{
                        ques[j]=1^right;
                    }
                    cnt++;
                }
                else{
                    ques[j]=s[j];
                }
            }
            door=tryCombination(ques);
            if(door==i){
                ng=mid;
            }
            else{
                ok=mid;
            }
        }
        int cnt=0;
        rep(j,N){
            if(s[j]==-1){
                if(cnt==ok)s[j]=right;
                d[j]=i;
                cnt++;
            }
        }
    }
    for(int i:s)cout<<i<<"\n";
    answer(s,d);
    /* ... */
}

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