Submission #561222

#	Time	Username	Problem	Language	Result	Execution time	Memory
561222		HappyPacMan	Cave (IOI13_cave)	C++14	100 / 100	1008 ms	588 KiB

cave

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

void exploreCave(int N){
    int comb[N],swt[N];
    memset(comb,-1,sizeof(comb));
    for(int i=0;i<N;i++){
        int z[N];
        for(int j=0;j<N;j++){
            z[j] = comb[j];
            if(z[j] == -1){
                z[j] = 1;
            }
        }
        int q = tryCombination(z);
        int st = 0;
        if(q == -1 || q > i){
            st = 1;
        }
        vector<int> pos;
        for(int j=0;j<N;j++){
            z[j] = comb[j];
            if(z[j] == -1){
                pos.emplace_back(j);
            }
        }
        int l = 0, r = pos.size()-1;
        while(l < r){
            int m = (l+r)/2;
            for(int i=0;i<=m;i++){
                z[pos[i]] = st;
            }
            for(int i=m+1;i<pos.size();i++){
                z[pos[i]] = st ^ 1;
            }
            q = tryCombination(z);
            if(q == -1 || q > i){
                r = m;
            }else{
                l = m+1;
            }
            for(int i=0;i<pos.size();i++){
                z[pos[i]] = -1;
            }
        }
        comb[pos[l]] = st;
        swt[pos[l]] = i;
    }
    answer(comb,swt);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:34:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             for(int i=m+1;i<pos.size();i++){
      |                           ~^~~~~~~~~~~
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<pos.size();i++){
      |                         ~^~~~~~~~~~~

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