제출 #844913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844913		RaresFelix	동굴 (IOI13_cave)	C++17	100 / 100	554 ms	608 KiB

cave

#include "cave.h"

const int MN = 5001;
int S[MN], D[MN], SUsa[MN], Guess[MN];
void exploreCave(int n) {
    for(int j = 0; j < n; ++j) 
        S[j] = D[j] = SUsa[j] = -1;
    for(int i = 0; i < n; ++i) { /// determinam usa i
        for(int j = 0; j < n; ++j) {
            if(S[j] == -1) {
                Guess[j] = 0;
            } else Guess[j] = S[j];
        }
        if(tryCombination(Guess) == i) { /// e bine
            SUsa[i] = 1;
        } else {
            SUsa[i] = 0;
        }
        int st = 0, dr = n - 1, mij;
        while(st < dr) {
            mij = (st + dr) / 2;
            for(int j = 0; j < n; ++j) {
                if(S[j] == -1) {
                    Guess[j] = 1 ^ SUsa[i] ^ (j > mij); /// garanteaza ca e inchisa, daca se afla inainte de mij
                } else
                    Guess[j] = S[j];
            }
            if(tryCombination(Guess) == i) {
                dr = mij;
            } else st = mij + 1;
        }
        D[st] = i;
        S[st] = SUsa[i];
    }
    answer(S, D);
}

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