Submission #287290

#	Time	Username	Problem	Language	Result	Execution time	Memory
287290		AMO5	Cave (IOI13_cave)	C++17	0 / 100	432 ms	504 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[]);
void answer(int s[],int d[]);

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;
	memset(s,0,sizeof(s));
	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){
	for(int i=0; i<n; i++){
		int C = color(i);
		dnc(0,n-1,C,i);
	}
	answer(s,d);
}
/*
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin>>n;
	exploreCave(n);
	return 0;
}
*/ 

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