제출 #710461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710461		Urvuk3	동굴 (IOI13_cave)	C++17	100 / 100	327 ms	460 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

#define EPS 1e-9
#define ll long long
const int INF=1e9,MAXN=3001;
const ll LINF=1e18,MOD=1e9+7;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define pb push_back
#define PRINTvec(niz) { cerr<<#niz<<"="; for(auto _i:niz) cerr<<_i<<" "; cerr<<endl; }

void exploreCave(int N){
    int S[N],D[N],mask[N];
    vector<bool> fixed(N,false);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(!fixed[j]) mask[j]=0;
        }
        int type=0;
        if(tryCombination(mask)==i){
            type=1;
            for(int j=0;j<N;j++) if(!fixed[j]) mask[j]=1;
        }
        //PRINT(i); PRINT(type);
        int l=0,r=N-1;
        while(l<r){
            int l1=l,r1=mid,l2=mid+1,r2=r;
            for(int j=l1;j<=r1;j++) if(!fixed[j]) mask[j]=!type;
            if(tryCombination(mask)!=i){
                l=l2,r=r2;
            }
            else{
                for(int j=l1;j<=r1;j++) if(!fixed[j]) mask[j]=type;
                for(int j=l2;j<=r2;j++) if(!fixed[j]) mask[j]=!type;
                l=l1,r=r1;
            }
        }
        //PRINT(l);
        S[l]=type;
        fixed[l]=true;
        D[l]=i;
        //cerr<<endl;
    }
    answer(S,D);
}

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