Submission #287306

#	Time	Username	Problem	Language	Result	Execution time	Memory
287306		AMO5	Cave (IOI13_cave)	C++17	100 / 100	1870 ms	760 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"

#define sz(x) (int)x.size()
using namespace std;
const int mxn = 5e3+5;
int n,s[mxn],d[mxn],c[mxn];
bool vis[mxn];
/*
int tryCombination(int s[]){
	for(int i=0; i<n; i++)
		cerr<<s[i]<<" ";
	cerr<<"\n";
	int x;
	cin>>x;
	return x;
}
void answer(int s[],int d[]){
	for(int i=0; i<n; i++)
	cerr<<s[i]<<" ";
	cerr<<"\n";
	for(int i=0; i<n; i++)
	cerr<<d[i]<<" ";
	cerr<<"\n";
}
// */ 

int color(int tar){
	int t = tryCombination(c);
	if(t==-1||t>tar)return 0;
	return 1;
}

void dnc(int le, int ri, int C, int tar){
	if(le==ri){
		d[le]=tar;
		vis[le]=1;
		c[le]=C;
		return;
	}
	int mid=(le+ri)/2;
	for(int i=0; i<n; i++)s[i]=0;
	for(int i=0; i<n; i++){
		if(le<=i&&i<=mid)
			s[i]=C;
		else 
			s[i]=1^C;
	}
	for(int i=0; i<n; i++)
		if(vis[i])s[i]=c[i];
	int t = tryCombination(s);
	if(t>tar||t==-1){
		dnc(le,mid,C,tar);
	}else{
		dnc(mid+1,ri,C,tar);
	}
}

void exploreCave(int N){
	n=N;
	for(int i=0; i<n; i++){
		int C = color(i);
		dnc(0,n-1,C,i);
	}
	answer(c,d);
}
/*
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	exploreCave(n);
	return 0;
}
// */ 

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