Submission #59390

#	Time	Username	Problem	Language	Result	Execution time	Memory
59390		spencercompton	Cave (IOI13_cave)	C++17	100 / 100	771 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
    /* ... */
    //tryCombination(int s);
    //answer(int s, int d)
    vector<int> rem;
    int n = N;
    int s[n];
    int d[n];
    for(int i = 0; i<n; i++){
    	s[i] = 0;
    	d[i] = -1;
    	rem.push_back(i);
    }
    for(int i = 0; i<n; i++){
    	int open = tryCombination(s);
    	if(open==-1 || open>i){
    		for(int j = 0; j<rem.size(); j++){
    			s[rem[j]] = 1-s[rem[j]];
    		}
    	}
    	//right now it is closed
    	int low = 0;
    	int high = rem.size()-1;
    	while(low<high){
    		int mid = (low+high)/2;
    		int t[n];
    		for(int j = 0; j<n; j++){
    			t[j] = s[j];
    		}
    		for(int j = 0; j<=mid; j++){
    			t[rem[j]] = 1-t[rem[j]];
    		}
    		open = tryCombination(t);
    		if(open==-1 || open>i){
    			high = mid;
    		}
    		else{
    			low = mid+1;
    		}

    	}
    	d[rem[low]] = i;
    	s[rem[low]] = 1-s[rem[low]];
    	vector<int> temp;
    	for(int j = 0; j<rem.size(); j++){
    		if(j==low){
    			continue;
    		}
    		temp.push_back(rem[j]);
    	}
    	rem = temp;
    }
    answer(s,d);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:20:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j<rem.size(); j++){
                      ~^~~~~~~~~~~
cave.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j = 0; j<rem.size(); j++){
                     ~^~~~~~~~~~~

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