제출 #472583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472583		Carmel_Ab1	Cave (IOI13_cave)	C++17	0 / 100	485 ms	588 KiB

cave

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld, ld> pld;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    os << "[";
    for (int i = 0; i < ll(a.size()); i++) { os << a[i] << ((i != ll(a.size() - 1) ? " " : "")); }
    os << "]\n";
    return os;
}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

#include "cave.h"
//#include "grader.c"

vi s,d;
void finish(){
    int n=s.size();
    int S[n],D[n];
    for(int i=0; i<n; i++)
        S[i]=s[i],D[i]=d[i];
    answer(S,D);
}
int ask(vi a){
    int n=a.size();
    int c[n];
    for(int i=0; i<n; i++)
        c[i]=a[i];
    return tryCombination(c);
}

void exploreCave(int n) {
    s.resize(n);
    d.resize(n);

    vector<bool>ok(n);
    for(int i=0; i<n; i++){
        int l=0,r=n-1,j=-1,p=0;//j opens door #i
        while(l<=r){
            int m=(l+r)/2;
            vi cur(s);
            int q1=ask(cur);
            for(int ll=0; ll<=m; ll++)
                if(!ok[ll])
                    cur[ll]^=1;
            int q2=ask(cur);

            if((q1==-1 && q2==-1) || (q2==-1 && q1>i) || (q1==-1 && q2>i) || (q1!=-1 && q2!=-1 && q1<=i && q2<=i)){
                l=m+1;
                continue;
            }
            r=m-1;
            j=m;
            if(q2>=i+1)
                p=1;
            else if(q1>=i+1)
                p=0;
            else if(q2==-1)
                p=1;
            else if(q1==-1)
                p=0;
        }

        d[j]=i;
        s[j]=p;
        ok[j]=1;
    }

    finish();
}

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