Submission #241183

#	Time	Username	Problem	Language	Result	Execution time	Memory
241183		abacaba	Cave (IOI13_cave)	C++14	100 / 100	1200 ms	1016 KiB

cave

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
#include "cave.h"
using namespace std;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
 
inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}
 
inline void setout(string s) {
    freopen(s.c_str(), "w", stdout);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

#define MAX_N 70000

bool used[MAX_N];
int cur;
int correct[MAX_N], door[MAX_N];
int s[MAX_N];
 
int ask_full(vector <int> now, int n, int c) {
    for(int i = 0; i < n; ++i)
        if(used[i])
            s[i] = correct[i];
    for(int i : now)
        s[i] = c;
    return tryCombination(s);
}
 
void rec(vector <int> now, int n, int right_c) {
    if(now.size() == 1) {
        correct[now[0]] = right_c;
        door[now[0]] = cur;
        used[now[0]] = true;
    }
    else {
        vector <int> temp = {};
        int mid = now.size() / 2;
        for(int i = 0; i < now.size(); ++i) {
            if(i < mid)
                temp.pb(now[i]);
            else {
                used[now[i]] = true;
                correct[now[i]] = right_c;
            }
        }
        int res = ask_full(temp, n, !right_c);
        for(int i : now)
            used[i] = false, correct[i] = -1;
        if(res == -1 || res > cur) {
            temp.clear();
            for(int i = mid; i < now.size(); ++i)
                temp.pb(now[i]);
        }
        rec(temp, n, right_c);
    }
}
 
void exploreCave(int n) {
    for(cur = 0; cur < n; ++cur) {
        vector <int> now = {};
        for(int j = 0; j < n; ++j)
            if(!used[j])
                now.pb(j);
        int x = ask_full(now, n, 1);
        rec(now, n, x == -1 || x > cur);
    }
    answer(correct, door);
}

Compilation message (stderr)

cave.cpp: In function 'void rec(std::vector<int>, int, int)':
cave.cpp:87:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < now.size(); ++i) {
                        ~~^~~~~~~~~~~~
cave.cpp:100:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = mid; i < now.size(); ++i)
                              ~~^~~~~~~~~~~~

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