제출 #1129568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129568		enzy	동굴 (IOI13_cave)	C++20	0 / 100	288 ms	604 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=5010;
int ja[maxn], pos[maxn], val[maxn];
bool check(int mid, int v, int n, int obj){
    int ask[n];
    for(int i=0;i<mid;i++) ask[i]=v;
    for(int i=mid;i<n;i++) ask[i]=1-v;
    for(int j=0;j<obj;j++) ask[pos[j]]=val[j];
    int x=tryCombination(ask);
    return x>obj;
}
void exploreCave(int n){
    memset(ja,0,sizeof(ja));
    int ans1[n], ans2[n];
    for(int i=0;i<n;i++){
        int ask[n];
        memset(ask,0,sizeof(ask));
        for(int j=0;j<i;j++) ask[pos[j]]=val[j];
        int a=tryCombination(ask), atval;
        if(a==-1||a>i) atval=0; // então o botão da porta i, tem q ser 0
        else atval=1;
        int l=0, r=n-1;
        while(l<r){
            int mid=(l+r)/2;
            if(check(mid,atval,n,i)) r=mid;
            else l=mid+1;
        }
        pos[i]=l;
        val[i]=atval;
        ja[l]++;
        ans1[l]=atval;
        ans2[l]=i;
    }
    answer(ans1,ans2);
}

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