제출 #573380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573380		talant117408	동굴 (IOI13_cave)	C++17	100 / 100	341 ms	552 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
 
int mod = 1e9+7;
 
ll modulo(ll a) {
    return ((a % mod) + mod) % mod;
}
 
ll add(ll a, ll b) {
    return modulo(a + b);
}
 
ll mult(ll a, ll b) {
    return modulo(a * b);
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) {
            res = mult(res, a);
        }
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 5003;
int known[N], pos[N], door[N];
//~ int _0or1[8] = {0, 1, 1, 0, 1, 0, 1, 1}, sw[8] = {7, 1, 4, 6, 5, 3, 0, 2};
 
//~ int tryCombination(int pos[]){
    //~ int closed = -1;
    //~ vector <int> opened(8);
    //~ for(int i = 0; i < 8; i++)
        //~ if(pos[i] == _0or1[i])
            //~ opened[sw[i]]++;
    //~ for(int i = 0; i < 8; i++){
        //~ if(!opened[i]){
            //~ closed = i;
            //~ break;
        //~ }
    //~ }
    //~ return closed;
//~ }
 
//~ void answer(int pos[], int door[]){
    //~ int i;
    //~ for(i = 0; i < 8; i++) cout << pos[i] << ' ';
    //~ cout << endl;
    //~ for(i = 0; i < 8; i++) cout << door[i] << ' ';
    //~ exit(0);
//~ }

//~ void exploreCave(int n);

//~ int main() {
    //~ int n;
    //~ cin >> n;
    //~ exploreCave(n);
    //~ printf("INCORRECT\nYour solution did not call answer().\n");
	//~ return 0;
//~ }

void exploreCave(int n) {
    for (int i = 0; i < n; i++) {
        int way = 0;
        for (int j = 0; j < n; j++) {
            if (!known[j]) pos[j] = 0;
        }
        auto res = tryCombination(pos);
        if (res == i) {
            way = 1;
            for (int j = 0; j < n; j++) {
                if (!known[j]) pos[j] = 1;
            }
        }
        
        int l = 0, r = n-1;
        while (l < r) {
            int mid = (l+r) >> 1;
            for (int j = mid+1; j <= r; j++) {
                if (!known[j]) pos[j] = 1-way;
            }
            auto res = tryCombination(pos);
            if (res == i) {
                for (int j = l; j <= r; j++) {
                    if (!known[j]) pos[j] = 1-pos[j];
                }
                l = mid+1;
            }
            else {
                r = mid;
            }
        }
        known[l] = 1;
        door[l] = i;
    }
    answer(pos, door);
}

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