Submission #776855

#	Time	Username	Problem	Language	Result	Execution time	Memory
776855		Sandarach151	Cave (IOI13_cave)	C++17	0 / 100	176 ms	444 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;

void exploreCave(int n) {
    pair<int, int> curans[n] = {{-1, -1}}; // for each door, what is switch number and position
    for(int i=0; i<n; i++){
        int arr[n];
        for(int j=0; j<n; j++){
            arr[j]=-1;
        }
        vector<int> rest;
        int spos;
        for(int j=0; j<i; j++){
            arr[curans[j].first]=curans[j].second;
        }
        for(int j=0; j<n; j++){
            if(arr[j]==-1){
                arr[j]=0;
                rest.push_back(j);
            }
        }
        tryCombination(arr)>i ? spos = 0 : spos = 1;
        if(spos==0){
            int lb = 0;
            int ub = rest.size()-1;
            while(lb!=ub){
                int mid = (lb+ub)/2;
                for(int j=lb; j<=mid; j++){
                    arr[rest[j]]=0;
                }
                for(int j=mid+1; j<=ub; j++){
                    arr[rest[j]]=1;
                }
                int temp = tryCombination(arr);
                temp>i || temp==-1 ? ub = mid : lb = mid+1;
            }
            curans[i]={rest[lb], spos};
        }
        else{
            int lb = 0;
            int ub = rest.size()-1;
            while(lb!=ub){
                int mid = (lb+ub)/2;
                for(int j=lb; j<=mid; j++){
                    arr[rest[j]]=1;
                }
                for(int j=mid+1; j<=ub; j++){
                    arr[rest[j]]=0;
                }
                int temp = tryCombination(arr);
                temp>i || temp==-1 ? ub = mid : lb = mid+1;
            }
            curans[i]={rest[lb], spos};
        }
    }
    int ans1[n];
    int ans2[n];
    for(int i=0; i<n; i++){
        ans1[curans[i].first] = i;
        ans2[curans[i].first] = curans[i].second;
    }
    answer(ans2, ans1);    
}

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