Submission #1101334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101334		alexander707070	Cave (IOI13_cave)	C++14	100 / 100	492 ms	844 KiB

cave

#include<bits/stdc++.h>
#define MAXN 5007
#include "cave.h"
using namespace std;

int n;
int s[MAXN],t[MAXN];
vector<int> unknown;
pair<int,int> ans[MAXN];

int ask(vector<int> z){
    for(int i=0;i<n;i++)s[i]=0;
    for(int i:z)s[i-1]=1;

    int curr=tryCombination(s);
    if(curr==-1)return n+1;
    return curr+1;
}

pair<int,int> findlever(int pos,vector<int> w){
    vector<int> toask;

    for(int i=1;i<pos;i++){
        if(ans[i].second==1)toask.push_back(ans[i].first);
    }

    int curr=ask(toask);

    if(curr>pos){
        int l=-1,r=w.size(),tt;
        while(l+1<r){
            tt=(l+r)/2;

            for(int f=0;f<=tt;f++){
                toask.push_back(w[f]);
            }

            if(ask(toask)==pos){
                r=tt;
            }else{
                l=tt;
            }

            for(int f=0;f<=tt;f++)toask.pop_back();
        }

        return {w[r],0};
    }else{
        int l=-1,r=w.size(),tt;

        while(l+1<r){
            tt=(l+r)/2;

            for(int f=0;f<=tt;f++){
                toask.push_back(w[f]);
            }

            if(ask(toask)>pos){
                r=tt;
            }else{
                l=tt;
            }

            for(int f=0;f<=tt;f++)toask.pop_back();
        }

        return {w[r],1};
    }
}

void exploreCave(int N) {
    n=N;

    for(int i=1;i<=n;i++)unknown.push_back(i);

    for(int i=1;i<=n;i++){
        ans[i]=findlever(i,unknown);

        for(int f=0;f<unknown.size();f++){
            if(unknown[f]==ans[i].first){
                swap(unknown[f],unknown[unknown.size()-1]);
                unknown.pop_back(); break;
            }
        }
    }

    for(int i=1;i<=n;i++){
        t[ans[i].first-1]=i-1;
        s[ans[i].first-1]=ans[i].second;
    }

    answer(s,t);
}

Compilation message (stderr)

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

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