Submission #701203

#	Time	Username	Problem	Language	Result	Execution time	Memory
701203		mychecksedad	Cave (IOI13_cave)	C++17	100 / 100	865 ms	588 KiB

cave

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

void answer(int S[], int D[]);
int tryCombination(int S[]);

void exploreCave(int N) {
    int s[N], a[N], b[N], C[N], d[N];
    vector<bool> vis(N, 0);
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j) if(!vis[j]) s[j] = 0;
        int f = tryCombination(s);
        if(f > i || f == -1){
            a[i] = 0;
        }else{
            a[i] = 1;
        }
        int l = 1, r = N - i;
        C[i] = 1;
        while(l <= r){
            int mid = l+r>>1;
            for(int j = 0, c = 0; j < N; ++j){
              if(!vis[j]){
            		c++;
                if(c >= l && c <= mid)
                  s[j] = a[i];
                else if(c > mid && c <= r)
                  s[j] = !a[i];
                else
              		s[j] = !a[i];  	
              }
            }
            int f = tryCombination(s);
            if(f > i || f == -1){
              C[i] = mid;
              r = mid - 1;
            }else{
              l = mid + 1;
            }
        }
        for(int j = 0, c = 0; j < N; ++j){
        	if(!vis[j]){
        		c++;
        		if(c == C[i]){
        			C[i] = j;
        			break;
        		}
        	}
        }
        s[C[i]] = a[i];
        vis[C[i]] = 1;
    }   
    for(int i = 0; i < N; ++i) b[C[i]] = i;
    for(int i = 0; i < N; ++i) d[C[i]] = a[i];

    answer(d, b);
}



#ifdef __cplusplus
#endif

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:22:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             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