Submission #919461

#	Time	Username	Problem	Language	Result	Execution time	Memory
919461		Gwynbleidd_	Cave (IOI13_cave)	C++14	100 / 100	391 ms	848 KiB

cave

#include "cave.h"

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> a, flip, pos;

int comb(){
    int q[n];
    for(int i=0;i<n;i++) q[i]=a[i];
    return tryCombination(q);
}

void answer(){
    int f[n], p[n];
    for(int i=0;i<n;i++) f[i]=flip[i], p[i]=pos[i];
    answer(f,p);
}

void exploreCave(int N) {
    n=N;
    flip.assign(n,-1);
    pos.assign(n,-1);
    a.assign(n,0);
    for(int t=0;t<n;t++){
        vector<int> ind;       
        for(int i=0;i<n;i++){
            if(flip[i]==-1){
                ind.push_back(i);
            }
            else{
                a[i]=flip[i];
            }
        }
        if(!ind.size()){
            break;
        }
        int last=comb();
        while(ind.size()>1){
            vector<int> l,r;
            for(int i=0;i<ind.size();i++){
                if(i<ind.size()/2){
                    l.push_back(ind[i]);
                }
                else{
                    r.push_back(ind[i]);
                }
            }
            for(auto &x:l){
                a[x]=1-a[x];
            }
            int x=comb();
            if(last==-1){
                swap(ind,l);
                last=x;
            }
            else if(last==x){
                swap(ind,r);
            }
            else if(x==-1||x>last){
                for(auto &x:l){
                    a[x]=1-a[x];
                }
                swap(ind,l);
            }
            else{
                swap(ind,l);
                last=x;
            }
        }
        if(last==-1){
            flip[ind[0]]=a[ind[0]];
            a[ind[0]]=1-a[ind[0]];
            pos[ind[0]]=comb();
        }
        else{
            flip[ind[0]]=1-a[ind[0]];
            pos[ind[0]]=last;
        }
    }
    answer();
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int i=0;i<ind.size();i++){
      |                         ~^~~~~~~~~~~
cave.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |                 if(i<ind.size()/2){
      |                    ~^~~~~~~~~~~~~

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