제출 #551506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551506		beedle	동굴 (IOI13_cave)	C++17	100 / 100	976 ms	528 KiB

cave

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#define pi 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 998244353ll
#define INF 1000000000000000000
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)

#include "cave.h"
 
using namespace std;

// int tryCombination(int s[])
// {
//     int n=4;
//     rep(i,0,n-1)
//     cout<<s[i]<<" ";
//     cout<<endl;
//     fflush(stdout);
//     int x;
//     cin>>x;
//     return x;
// }

// void answer(int s[], int d[])
// {
//     int n=4;
//     rep(i,0,n-1)
//     cout<<s[i]<<" ";
//     cout<<endl;
//     rep(i,0,n-1)
//     cout<<d[i]<<" ";
//     cout<<endl;
//     fflush(stdout);
// }

void exploreCave(int n)
{
    bool known[n];
    rep(i,0,n-1)
    known[i]=false;
    int actual[n];
    int binding[n];
    
    vector <int> idx;
    rep(i,0,n-1)
    idx.pb(i);

    rep(door,0,n-1)
    {
        int q[n];
        for(auto x:idx)
        q[x]=0;
        rep(i,0,n-1)
        if(known[i])
        q[i]=actual[i];

        int ans=tryCombination(q);
        int expected;
        if(ans==-1 || ans>door)
        expected=0;
        else
        expected=1;

        int lo=0;
        int hi=sz(idx)-1;

        while(hi-lo!=0)
        {
            int mid=(lo+hi)/2;

            rep(i,0,n-1)
            if(known[i])
            q[i]=actual[i];

            rep(i,lo,mid)
            q[idx[i]]=expected;
            rep(i,mid+1,hi)
            q[idx[i]]=1^expected;

            ans=tryCombination(q);

            if(ans==-1 || ans>door)
            {
                hi=mid;
            }
            else
            {
                lo=mid+1;
            }
        }

        known[idx[hi]]=true;
        binding[idx[hi]]=door;
        actual[idx[hi]]=expected;

        // cout<<"SAYING"<<endl;
        // cout<<idx[hi]<<" "<<expected<<endl<<endl;

        vector <int> nidx;
        for(auto x:idx)
        if(x!=idx[hi])
        nidx.pb(x);

        idx=nidx;
    }

    answer(actual,binding);
}

// signed main()
// {
//     // fast;

//     // freopen("milkorder.in","r",stdin);
//     // freopen("milkorder.out","w",stdout);

//     exploreCave(4);

//     return 0;
// }

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