Submission #899261

#	Time	Username	Problem	Language	Result	Execution time	Memory
899261		aykhn	동굴 (IOI13_cave)	C++17	0 / 100	2027 ms	608 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
 
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
    ios_base::sync_with_stdio(0);\
    cin.tie(0);\
    cout.tie(0)\
 
void exploreCave(int n){
    int type[n], ind[n], qry[n];
    map<int, int> done;
    for(int i = 0; i < n; i++){
        int l = 0, r = n - 1, index, p;
        for(int j = 0; j < n; j++){
            if(done.count(j)){
                qry[j] = done[j];
            }
            else{
                qry[j] = 0;
            }
        }
        if(tryCombination(qry) >= i + 1){
            p = 0;
        }
        else{
            p = 1;
        }
        while(l < r){
            int mid = (l + r) / 2;
            for(int j = 0; j < n; j++){
                if(done.count(j)){
                    qry[j] = done[j];
                  	continue;
                }
              	if (l <= j && j <= mid){
                  	qry[j] = p;
                }
              	else if (mid < j && j <= r) qry[j] = 1 - p;
            }
            if(tryCombination(qry) >= i + 1){
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
        done[l] = p;
        type[l] = p;
        ind[l] = i;
    }
    answer(type, ind);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:24:31: warning: unused variable 'index' [-Wunused-variable]
   24 |         int l = 0, r = n - 1, index, p;
      |                               ^~~~~

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