Submission #350090

#	Time	Username	Problem	Language	Result	Execution time	Memory
350090		tjrwodnjs999	Cave (IOI13_cave)	C++11	100 / 100	435 ms	876 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int getans(int input[]){
    int ans=tryCombination(input);
    return ans==-1?n:ans;
}
void exploreCave(int N) {
    n=N;
    int arr[N],pos[N],qry[N];
    fill(arr,arr+N,-1);
    for(int i=0;i<N;i++){
        vector<int> vt;
        for(int j=0;j<N;j++){
            if(arr[j]==-1) vt.push_back(j);
            else qry[j]=pos[j];
        }
        int cur;
        for(int j:vt) qry[j]=0;
        int tr=getans(qry);
        if(tr>i) cur=0;
        else cur=1;
        for(int j:vt) qry[j]=1-cur;
        int l=0,r=vt.size()-1;
        while(l<=r){
            if(l==r) {arr[vt[l]]=i,pos[vt[l]]=cur;break;}
            int mid=l+r>>1;
            for(int i=l;i<=mid;i++) qry[vt[i]]=cur;
            int ans=getans(qry);
            for(int i=l;i<=mid;i++) qry[vt[i]]=1-cur;
            if(ans>i) r=mid;
            else l=mid+1;
        }
    }
    answer(pos,arr);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:28:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |             int mid=l+r>>1;
      |                     ~^~

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