제출 #306290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306290		talant117408	동굴 (IOI13_cave)	C++17	0 / 100	163 ms	536 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);
/*
bool tryCombination(vector <int> pos){
    return true;
}

void answer(vector <int> pos, vector <int> door){
    for(auto to : pos) cout << to << ' ';
    cout << endl;
    for(auto to : door) cout << to << ' ';
}*/

bool check(int pos[], int truepos, int l, int r){
    for(int i = l; i <= r; i++){
        if(used[i]) continue;
        pos[i] = truepos;
    }
    return tryCombination(pos);
}
/*
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){
    int pos0[n], pos1[n], doornum[n];
    for(int i = 0; i < n; i++) pos1[i] = 1;
    for(int door = 0; door < n; door++){
        int truepos = 1;
        int closed = tryCombination(pos0);
        if(closed == -1 || closed > door) truepos--;
        
        int l = 0, r = n-1;
        while(l < r){
            int mid = (l+r)>>1;
            
            if(check((truepos ? pos0 : pos1), truepos, l, mid)){
                r = mid;
            }
            else{
                l = mid+1;
            }
        }
        used[l]++;
        doornum[l] = door;
        pos0[l] = pos1[l] = truepos;
    }
    
    answer(pos0, doornum);
}

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