제출 #1299399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1299399		TrinhKhanhDung	동굴 (IOI13_cave)	C++20	12 / 100	113 ms	584 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;

void exploreCave(int n){
    int S[n], D[n];
    for(int i = 0; i < n; i++){
        S[i] = 0;
        D[i] = -1;
    }
    vector<int> a(n);
    iota(a.begin(), a.end(), 0);
    for(int t = 0; t < n; t++){
        for(int x: a){
            S[x] = 0;
        }
        int x = tryCombination(S);
        if(x != -1 && x <= t){
            for(int x: a){
                S[x] = 1;
            }
        }
        int l = 0, r = (int)a.size() - 1;
        while(l < r){
            int m = (l + r) >> 1;
            for(int i = l; i <= m; i++){
                S[a[i]] = !S[a[i]];
            }
            int x = tryCombination(S);
            if(x != -1 && x <= t){
                for(int i = l; i <= m; i++){
                    S[a[i]] = !S[a[i]];
                }
                r = m;
            }
            else{
                l = m + 1;
            }
        }
        x = a[r];
        D[t] = x;
        vector<int> b;
        for(int y: a){
            if(y != x){
                b.push_back(y);
            }
        }
        a = b;
    }
    answer(S, D);
}

//int main(){
//    ios_base::sync_with_stdio(0); cin.tie(0);
//
//    exploreCave(4);
//
//    return 0;
//}

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