제출 #131213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131213		Blagojce	Cave (IOI13_cave)	C++11	0 / 100	99 ms	516 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;
/*
                int l = i;
                int r = N - 1;

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

                        if(q <= i){
                                l = mid + 1;
                        }
                        else{
                                r = mid;
                        }
                }*/
                ANS[i] = t;
                ASK[i] = t;
                //ANS2[i] = l;
        }
        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){
                                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;
                        }
                }
                ANS2[i] = l;
        }

        answer(ANS, ANS2);
}

• 서브태스크 1: 0 / 12
• 서브태스크 2: 0 / 13
• 서브태스크 3: 0 / 21
• 서브태스크 4: 0 / 30
• 서브태스크 5: 0 / 24