Submission #350073

#	Time	Username	Problem	Language	Result	Execution time	Memory
350073		tjrwodnjs999	Cave (IOI13_cave)	C++11	0 / 100	218 ms	620 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int arr[5005],pos[5005],qry[5005];
void exploreCave(int N) {
    fill(arr,arr+5005,-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=tryCombination(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[l]=i,pos[l]=cur;break;}
            int mid=l+r>>1;
            for(int i=l;i<=mid;i++) qry[vt[i]]=cur;
            int ans=tryCombination(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:22:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             int mid=l+r>>1;
      |                     ~^~

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