Submission #1216822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216822		matere	Cave (IOI13_cave)	C++20	100 / 100	173 ms	604 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int n){
    vector<int>v;
    for(int i=0;i<n;i++){
        v.push_back(i);
    }
    int ans[n],d[n];
    for(int i=0;i<n;i++) ans[i]=0;
    int cnt=0;
    while(v.size()){
        bool rev=false;
        int cur=tryCombination(ans);
        if(cur!=cnt) rev=true;
        vector<int>v1=v;
        while(v1.size()>1){
            vector<int>v2,v3;
            for(int i=0;i<v1.size()/2;i++){
                v2.push_back(v1[i]);
            }
            for(int i=v1.size()/2;i<v1.size();i++){
                v3.push_back(v1[i]);
            }
            for(int i=0;i<v2.size();i++){
                ans[v2[i]]=0;
            }
            for(int i=0;i<v3.size();i++){
                ans[v3[i]]=1;
            }
            // for(int i:v2) cout<<i<<' ';
            // cout<<endl;
            // for(int i:v3) cout<<i<<' ';
            // cout<<endl;
            // for(int i:ans) cout<<i<<' ';
            // cout<<endl;
            int k=tryCombination(ans);
            // cout<<"---"<<k<<endl;
            if(!rev){
                if(k!=cnt){
                    v1=v3;
                }
                else{
                    v1=v2;
                }
            }
            else{
                if(k==cnt){
                    v1=v3;
                }
                else{
                    v1=v2;
                }
            }
            for(int i=0;i<v3.size();i++){
                ans[v3[i]]=0;
            }
        }
        // cout<<v1[0]<<endl;
        d[v1[0]]=cnt;
        ans[v1[0]]=1-rev;
        v.erase(lower_bound(v.begin(),v.end(),v1[0]));
        cnt++;
    }
    answer(ans,d);
}

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