Submission #995427

#	Time	Username	Problem	Language	Result	Execution time	Memory
995427		saddd	Cave (IOI13_cave)	C++17	100 / 100	431 ms	852 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int n;
void exploreCave(int N) {
    n = N;
    int ask[n] = {}, anss[n] = {}, ansd[n] = {}, ress[n] = {}, resd[n] = {};
    bool seen[n];
    for(int i = 0; i < n; i++)seen[i] = 0;
    for(int i = 0; i < n; i++){
        // door to switch 
        for(int j = 0; j < i; j++){
            ask[ansd[j]] = anss[j];
        }
        for(int j = 0; j < n; j++){
            if(!seen[j])ask[j] = 0;
        }
        int v = tryCombination(ask); 
        //for(int j = 0; j < n; j++)cout << ask[j] << " ";
        //cout << v << "\n";
        if(v == -1 || v > i){
            anss[i] = 0;
        }else{
            anss[i] = 1;
        }
        int l = 0, r = n - 1;
        while(l <= r){
            int mid = (l + r) >> 1;
            for(int j = 0; j < mid; j++){
                if(!seen[j])ask[j] = !anss[i];
            }
            for(int j = mid; j < n; j++){
                if(!seen[j])ask[j] = anss[i];
            }
            int v = tryCombination(ask);
            if(v == -1 || v > i){
                ansd[i] = mid; l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        seen[ansd[i]] = 1;
    }
    
    //switch to door 
    for(int i = 0; i < n; i++){
        ress[ansd[i]] = anss[i]; resd[ansd[i]] = i;
    }
    answer(ress, resd);
}

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