제출 #131230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131230		Blagojce	동굴 (IOI13_cave)	C++11	100 / 100	504 ms	640 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];

        bool MATCHED[N];
        memset(MATCHED, false, sizeof(MATCHED));
        
        fr(i, 0, N){
                int t = 0;
                fr(j, 0, N){
                        if(MATCHED[j]) ASK[j] = ANS[j];
                        else ASK[j] = 0;
                }
                int q = tryCombination(ASK);
                if(q == -1){
                        q = N;
                }
                if(q <= i){
                        t = 1;
                }

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

                        int q = tryCombination(ASK);
                        if(q == -1){
                                q = N;
                        }
                        
                        if(q <= i){
                                l = mid + 1;
                        }
                        else{
                                r = mid;
                        }
                }
                MATCHED[l] = true;
                ANS[l] = t;

                ANS2[l] = i;
        }

        answer(ANS, ANS2);
}

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