Submission #394111

#	Time	Username	Problem	Language	Result	Execution time	Memory
394111		teehandsome	Cave (IOI13_cave)	C++11	100 / 100	1300 ms	708 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxn=5010;
int ans_pos[mxn]; //the door 'switch i' connect to
int ans_dir[mxn]; //correct direction of 'switch i'
int arr[mxn];
int N;

void setall(vector<int> &ar,int val) {
//    debug(ar);
    for(int i=0;i<N;i++) {
        if(ans_dir[i]!=-1) arr[i]=ans_dir[i];
        else arr[i]=!val;
    }
    for(auto e:ar) arr[e]=val;
}
int debug_index=-1;

int solve(vector<int> ar,int correct,int curans) {
    if(curans==debug_index) debug(ar),debug(correct);
    int sz=ar.size();
    if(sz==1) {
//        setall(ar,correct);
//        int temp=tryCombination(arr);
//        assert(temp>curans);
        return ar[0];
    }
    int l=0,r=sz-1;
    int mid=(l+r)/2;
    vector<int> arL,arR;
    for(int i=0;i<=mid;i++) arL.push_back(ar[i]);
    for(int i=mid+1;i<sz;i++) arR.push_back(ar[i]);
    if(curans==debug_index) {
        debug(arL);
        debug(arR);
    }
    setall(arL,correct);
    if(curans==debug_index) {
        cout<<"[";
        for(int i=0;i<N;i++) {
            if(i) cout<<",";
            cout<<arr[i];
        }
        cout<<"]"<<endl;
    }
    int temp=tryCombination(arr);
    if(curans==debug_index) debug(temp);
    if(temp>curans or temp==-1) return solve(arL,correct,curans);
    return solve(arR,correct,curans);
}

void exploreCave(int n) {
    N=n;
    memset(ans_pos,-1,sizeof(ans_pos));
    memset(ans_dir,-1,sizeof(ans_dir));
    for(int t=0;t<n;t++) {
        vector<int> ar;
        for(int i=0;i<n;i++) {
            if(ans_pos[i]==-1) {
                ar.push_back(i);
            }
        }
        assert(ar.size()==n-t);
        setall(ar,1);
        int temp=tryCombination(arr);
        int correct;
        if(temp==t) correct=0;
        else correct=1;
        if(t==debug_index) debug(correct);
        int idx=solve(ar,correct,t);
        ans_pos[idx]=t;
        ans_dir[idx]=correct;
        vector<int> cur_pos(ans_pos,ans_pos+n);
        vector<int> cur_dir(ans_dir,ans_dir+n);
//        debug(t);
//        debug(cur_pos);
//        debug(cur_dir);
    }
    answer(ans_dir,ans_pos);
}

Compilation message (stderr)

In file included from /usr/include/c++/9/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/9/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/9/ext/pb_ds/assoc_container.hpp:48,
                 from cave.cpp:3:
cave.cpp: In function 'void exploreCave(int)':
cave.cpp:93:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |         assert(ar.size()==n-t);
      |                ~~~~~~~~~^~~~~

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