Submission #1121298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121298		PagodePaiva	Cave (IOI13_cave)	C++17	100 / 100	148 ms	772 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"

using namespace std;

const int N = 5000;
int c[N];
int d[N];

int query(int ask[]){
    /*for(int i = 0;i < 4;i++){
        cout << ask[i] << ' ';
    }
    cout << '\n';*/
    int d = tryCombination(ask);
    return d;
}

void exploreCave(int n) {
    int ask[n];
    for(int i = 0;i < n;i++){
        ask[i] = 0;
    }
    int t;
    vector <int> v;
    for(int i = 0;i <n;i++){
        v.push_back(i);
    }
    t = query(ask);
    for(int i = 0;i < n;i++){
        int l = 0, r = v.size()-1;
        while(l < r){
            int mid = (l+r)/2;
            for(int j = l;j <= mid;j++){
                ask[v[j]] ^= 1;
            }
            int tt = query(ask);
            if(t == i and tt == i){
                l = mid+1;
            }
            else if(t == i and tt != i){
                r = mid;
            }
            else if(t != i and tt != i){
                l = mid+1;
            }
            else{
                r = mid;
            }
            t = tt;
        }
        c[i] = v[l];
        if(t != i) d[i] = ask[v[l]];
        else{
            ask[v[l]] ^= 1;
            d[i] = ask[v[l]];
            t = query(ask);
        }
        vector <int> vv;
        for(int j = 0;j < v.size();j++){
            if(v[l] == v[j]) continue;
            vv.push_back(v[j]);
        }
        v = vv;
    }
    int res1[n], res2[n];
    for(int i = 0;i < n;i++){
        res1[c[i]] = i;
        res2[c[i]] = d[i];
    }
    answer(res2, res1);
    return;
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:60:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int j = 0;j < v.size();j++){
      |                       ~~^~~~~~~~~~

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