Submission #537089

#	Time	Username	Problem	Language	Result	Execution time	Memory
537089		fuad27	Cave (IOI13_cave)	C++17	100 / 100	412 ms	588 KiB

cave

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

template<typename T>
auto operator<<(ostream &os, T&v)->decltype(v.begin(), os){
	os << "[";
	int f = 0;
	for(auto i:v) {
		if(f++)os << ", ";
		os << i;
	}
	os << "]";
	return os;
}
template<typename F, typename S>
ostream& operator<<(ostream &os, pair<F, S> const &p) {
	return os << "(" << p.first << ", " << p.second << ")";
}
ostream& operator<<(ostream &os, string s) {
	for(char i:s){
		os << i;
	}
	return os;
}
void debug(){}
template<typename T, typename... V>
void debug(T t, V... v) {
	cerr << t;
	if(sizeof...(v)) {
		cerr << ", "; debug(v...);
	}
}
#ifdef LOCAL
#define dbg(x...) cerr << "[" << #x << "]: " << "["; debug(x); cerr << "]\n";
#else
#define dbg(x...)
#endif




vector<int> used;
vector<int> numbers;
vector<int> ans1;
vector<int> ans2;
int check = false;

int query(vector<int> t) {
	int num[t.size()];
	for(int i = 0;i<t.size();i++) {
		num[i] = t[i];
	}
	int ans = tryCombination(num);
	if(ans == -1)return t.size();
	return ans;
}


void change(int l, int r) {
	for(int i = l;i<=r;i++) {
		if(used[i])continue;
		numbers[i]=1^numbers[i];
	}
}

void find(int k, int n, int l, int r) {
	if(l == r) {
		dbg(l, r, k);
		used[l] = true;
		ans1[l] = k;
		numbers[l] = 1^numbers[l];
	}
	else {
		int mid = (l+r)/2;
		change(l, mid);
		int q = query(numbers);
		dbg(k, l, r, q, numbers);
		change(l, mid);
		if(q > k) {
			find(k, n, l, mid);
		}
		else {
			find(k, n, mid+1, r);
		}
	}
}


void exploreCave(int N) {
	int a1[N], a2[N];
	numbers = used = ans1 = ans2 = vector<int> (N, 0);
	for(int i = 0;i<N;i++) {
		if(query(numbers) > i) {
			change(0, N-1);
		}
		find(i, N, 0, N-1);
	}
	for(int i = 0;i<N;i++) {
		a1[i] = ans1[i];
		a2[i] = numbers[i];
	}
	answer(a2, a1);
}

Compilation message (stderr)

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

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