제출 #131216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131216		Blagojce	동굴 (IOI13_cave)	C++11	12 / 100	363 ms	584 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];
        int ASK[N];
        fr(i, 0, N){
                int t = 0;
                fr(j, i, N){
                        ASK[j] = 0;
                }
                int q = tryCombination(ASK);
                if(q == -1) q = N + 1;

                if(q <= i) t = 1;

                ANS[i] = t;
                ASK[i] = t;
                ANS2[i] = i;
        }
        bool MATCHED[N];
        memset(MATCHED, false, sizeof(MATCHED));
        fr(i, 0, N){
                int l = 0, r = N - 1;
                fr(j, 0, N) ASK[j] = ANS[j];

                while(l < r){
                        int mid = (l + r) / 2;
                        fr(j, l, mid + 1){
                                if(MATCHED[j]) continue;
                                ASK[j] = ANS[j] ^ 1;
                        }

                        int q = tryCombination(ASK);
                        if(q == -1) q = N + 1;

                        fr(j, l, mid + 1){
                                ASK[j] = ANS[j];
                        }

                        if(q <= i){
                                r = mid;
                        }
                        else{
                                l = mid + 1;
                        }
                }
                MATCHED[l] = true;
                ANS2[i] = l;
        }
        answer(ANS, ANS2);
}

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