제출 #1257270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257270		FernandoJC07	동굴 (IOI13_cave)	C++20	100 / 100	211 ms	588 KiB

cave

#include <bits/stdc++.h>
//#include "greader.h"
#include "cave.h"
#define vi vector<int>
#define vii vector<vi>
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vpii vector<pii>
#define forn(i, n) for(int i = 0; i<n; ++i)
#define For(i, a, n) for(int i = a; i<n; ++i)
using namespace std;

void exploreCave(int N){
    int S[N], D[N];
    forn(i, N) { S[i] = D[i] = -1;}
    forn(door, N){
        int q[N];
        vi oo;
        forn(i, N){
            if(S[i] != -1) q[i] = S[i];
            else {q[i] = 0; oo.pb(i);}
        }
        int val1 = tryCombination(q);
        int s;
        if(val1 == door) s = 1; else s= 0;
        int l = 0, r = oo.size()-1;
        while(r>l){
            int mid = l + (r-l)/2;         
            for(int x: oo) q[x] = 1-s;
            For(i, l, mid+1){
                q[oo[i]] = s;
            }
            //dbg(mid);
            int val2 = tryCombination(q);
            //dbg(val2);
            if(val2 == door) l=mid+1;
            else r = mid;
        }
        D[oo[l]] = door;
        S[oo[l]] = s;
        /*dbg(oo[l]);
        dbg(S[oo[l]]);
        dbg(D[oo[l]]);*/
    }
    answer(S, D);
}

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