Submission #1359310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359310		osmiyum	Cave (IOI13_cave)	C++20	100 / 100	186 ms	540 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int n){
    vector<int> siralama(n+1, -1);
    vector<int> durum(n+1, -1);
    for(int i = 0; i < n; i++){
        int s[n];
        for(int j = 0; j < n; j++){
            s[j] = 0;
        }
        for(int j = 0; j < i; j++){
            s[siralama[j]] = durum[j];
        }
        if(tryCombination(s) == i){
            durum[i] = 1;
        }
        else{
            durum[i] = 0;
        }
        int l = 0;
        int r = n - 1;
        int res = -1;
        while(l < r){
            int mid = (l + r)/2;
            int s2[n];
            for(int j = 0; j < n; j++){
                s2[j] = 1 - durum[i];
            }
            for(int j = l; j <= mid; j++){
                s2[j] = durum[i];
            }
            for(int j = 0; j < i; j++){
                s2[siralama[j]] = durum[j];
            }
            if(tryCombination(s2) == i){
                l = mid + 1;
            }
            else{
                r = mid;
            }
        }
        siralama[i] = l;
    }
    int d[n];
    int durumcev[n];
    for(int i = 0; i < n; i++){
        d[siralama[i]] = i;
    }
    for(int i = 0; i < n; i++){
        durumcev[i] = durum[d[i]];
    }
    answer(durumcev, d);
}

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