Submission #131207

#	Time	Username	Problem	Language	Result	Execution time	Memory
131207		Blagojce	Cave (IOI13_cave)	C++11	0 / 100	375 ms	464 KiB

cave

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x),end(x)
#define what_is(x) cout<<#x<<' '<<x<<endl

#include "cave.h"

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-9;

void exploreCave(int N) {
        int ANS[N];
        int ANS2[N];
        memset(ANS, -1, sizeof(ANS));
        int ASK[N];
        fr(i, 0, N){
                int t = 0;
                fr(j, 0, N){
                        if(ANS[j] == -1) ASK[j] = 0;
                        else ASK[j] = ANS[j];
                }
                int q = tryCombination(ASK);
                if(q == -1) q = N + 1;
                if(q <= i) t = 1;
                int l = 0;
                while(ANS[l] != -1) l ++;
                int r = N - 1;
                while(ANS[r] != -1) r --;
                while(l < r){
                        int mid = (l + r) / 2;
                        fr(j, l, mid + 1){
                                if(ANS[j] != -1) continue;
                                ASK[j] = t;
                        }
                        fr(j, mid + 1, r + 1){
                                if(ANS[j] != -1) continue;
                                ASK[j] = (t ^ 1);
                        }
                        q = tryCombination(ASK);
                        if(q == -1) q = N + 1;

                        if(q <= i){
                                r = mid;
                        }
                        else{
                                l = mid + 1;
                        }
                        while(ANS[l] != -1) l ++;
                        while(ANS[r] != -1) r --;
                }
                ANS[i] = t;
                ANS2[l] = i;
        }
        answer(ANS, ANS2);
}

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