oj.uz

Submission #318779

# Submission time Handle Problem Language Result Execution time Memory
318779 2020-11-03T08:09:40 Z Haruto810198 Cave (IOI13_cave) C++17
12 / 100
 903 ms 868 KB 
#include <bits/stdc++.h>

/******/
#include "cave.h"
/******/

using namespace std;

//#define int long long
#define double long double

#define vi vector<int>
#define pii pair<int,int>
#define si set<int>
#define mii map<int,int>

#define F first
#define S second

#define pb push_back
#define pf push_front
#define eb emplace_back
#define ef emplace_front
#define pob pop_back
#define pof pop_front

const int INF=2147483647;
const int MOD=1000000007;
const int mod=998244353;
const double eps=1e-12;

/******

int tryCombination(int guess[]){

    cout<<"? ";
    for(int i=0;i<4;i++){
        cout<<guess[i]<<" ";
    }
    cout<<endl;

    int ret;
    cin>>ret;
    return ret;
}

void answer(int state[],int pos[]){

    cout<<"!"<<endl;
    for(int i=0;i<4;i++){
        cout<<state[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<4;i++){
        cout<<pos[i]<<" ";
    }
    cout<<endl;

}

******/

void exploreCave(int n){

    int state[n],pos[n];
    int guess[n];
    int ans;

    for(int j=0;j<n;j++){
        state[j]=-1;
    }

    for(int i=0;i<n;i++){

        for(int j=0;j<n;j++){
            guess[j]=0;
        }
        for(int j=0;j<i;j++){
            guess[ pos[j] ]=state[j];
        }
        ans=tryCombination(guess);
        if( ans>i or ans==-1 ){
            state[i]=0;
        }
        else{
            state[i]=1;
        }

        int l=0,r=n-1,mid;
        while(l<r){

            mid=(l+r)/2;

            /***debug***
            cout<<l<<" "<<r<<" "<<mid<<endl;
            ***debug***/

            for(int j=0;j<n;j++){
                guess[j]=1-state[i];
            }
            for(int j=l;j<=mid;j++){
                guess[j]=state[i];
            }
            for(int j=0;j<i;j++){
                guess[ pos[j] ]=state[j];
            }

            ans=tryCombination(guess);
            if(ans>i or ans==-1){
                r=mid;
            }
            else{
                l=mid+1;
            }

        }
        pos[i]=l;

        /***debug***
        cout<<"//"<<endl;
        for(int i=0;i<n;i++){
            cout<<state[i]<<" ";
        }
        cout<<endl;
        for(int i=0;i<n;i++){
            cout<<pos[i]<<" ";
        }
        cout<<endl;
        cout<<"//"<<endl;
        ***debug***/

    }

    answer( state , pos );

}

/******

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    exploreCave(n);

    return 0;
}

******/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 584 KB Output is correct
2 Correct 565 ms 484 KB Output is correct
3 Correct 885 ms 612 KB Output is correct
4 Correct 615 ms 492 KB Output is correct
5 Correct 893 ms 628 KB Output is correct
6 Correct 874 ms 636 KB Output is correct
7 Correct 903 ms 868 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 886 ms 512 KB Output is correct
13 Correct 878 ms 612 KB Output is correct
14 Correct 882 ms 868 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 484 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 890 ms 740 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 894 ms 492 KB Answer is wrong
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Incorrect 1 ms 364 KB Answer is wrong
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Incorrect 1 ms 364 KB Answer is wrong
6 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 584 KB Output is correct
2 Correct 565 ms 484 KB Output is correct
3 Correct 885 ms 612 KB Output is correct
4 Correct 615 ms 492 KB Output is correct
5 Correct 893 ms 628 KB Output is correct
6 Correct 874 ms 636 KB Output is correct
7 Correct 903 ms 868 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 886 ms 512 KB Output is correct
13 Correct 878 ms 612 KB Output is correct
14 Correct 882 ms 868 KB Output is correct
15 Correct 901 ms 484 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 890 ms 740 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Incorrect 894 ms 492 KB Answer is wrong
21 Halted 0 ms 0 KB -