제출 #306353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306353		talant117408	동굴 (IOI13_cave)	C++17	100 / 100	576 ms	636 KiB

cave

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

using namespace std;

#define pb push_back
#define mp make_pair

const int N = 5003;
vector <int> used(N);/*

int _0or1[8] = {0, 1, 1, 0, 1, 0, 1, 1}, sw[8] = {7, 1, 4, 6, 5, 3, 0, 2};

int tryCombination(int pos[]){
    int closed = -1;
    vector <int> opened(8);
    for(int i = 0; i < 8; i++)
        if(pos[i] == _0or1[i])
            opened[sw[i]]++;
    for(int i = 0; i < 8; i++){
        if(!opened[i]){
            closed = i;
            break;
        }
    }
    return closed;
}

void answer(int pos[], int door[]){
    int i;
    for(i = 0; i < 8; i++) cout << pos[i] << ' ';
    cout << endl;
    for(i = 0; i < 8; i++) cout << door[i] << ' ';
    exit(0);
}*/

int check(vector <int> pos, int truepos, int l, int r){
    int n = pos.size();
    for(int i = l; i <= r; i++){
        if(used[i]) continue;
        pos[i] = truepos;
    }
    int poss[n];
    for(int i = 0; i < n; i++)
        poss[i] = pos[i];
    return tryCombination(poss);
}
/*
void exploreCave(int n);

int main() {
    int N;
    cin >> N;
	exploreCave(N);
    printf("INCORRECT\nYour solution did not call answer().\n");
	return 0;
}*/

void exploreCave(int n){
    vector <int> pos0(n), pos1(n), doornum(n);
    for(int i = 0; i < n; i++) pos1[i] = 1, pos0[i] = 0;
    
    for(int door = 0; door < n; door++){
        int truepos = 1;
        int poss[n];
        for(int i = 0; i < n; i++) poss[i] = pos0[i];
        int closed = tryCombination(poss);
        if(closed == -1 || closed > door) truepos--;
        
        int l = 0, r = n-1;
        while(l < r){
            int mid = (l+r)>>1;
            closed = check((truepos ? pos0 : pos1), truepos, l, mid);
            
            if(closed == -1 || closed > door){
                r = mid;
            }
            else{
                l = mid+1;
            }
        }
        used[l]++;
        doornum[l] = door;
        pos0[l] = pos1[l] = truepos;
    }
    
    int dooor[n], poss[n];
    for(int i = 0; i < n; i++){
        dooor[i] = doornum[i];
        poss[i] = pos0[i];
    }
    
    answer(poss, dooor);
}

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