Submission #579325

#	Time	Username	Problem	Language	Result	Execution time	Memory
579325		MrDeboo	Cave (IOI13_cave)	C++17	0 / 100	261 ms	468 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int Try(vector<int>v){
    int a[v.size()];
    for(int i=0;i<v.size();i++)a[i]=v[i];
    int k=tryCombination(a);
    if(k==-1)return v.size();
    return k;
}
void exploreCave(int n){
    int a[n],b[n];
    memset(a,-1,sizeof a);
    memset(b,-1,sizeof b);
    for(int i=1;i<=n;i++){
        vector<int>v(n,1);
        for(int w=0;w<n;w++){
            if(a[w]!=-1)v[w]=a[w];
        }
        if(Try(v)>=i){
            for(int w=0;w<n;w++){
                if(a[w]==-1)v[w]=0;
            }
        }
        int l=0,r=n-i,mid,f=0;
        while(l<=r){
            mid=(l+r)/2;
            vector<int>vc=v;
            int cur=mid;
            for(int w=0;w<n;w++){
                if(a[w]==-1){
                    vc[w]^=1;
                    if(cur--==0)break;
                }
            }
            if(Try(vc)<i)l=mid+1;
            else {r=mid-1;f=mid;}
        }
        for(int w=0;w<n;w++){
            if(f--==0){
                a[w]=(v[w]^1);
                b[w]=i;
                break;
            }
        }
    }
    answer(a,b);
}

Compilation message (stderr)

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

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