Submission #969857

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969857	2024-04-25T17:28:05 Z	elotelo966	Cave (IOI13_cave)	C++17	12 / 100	808 ms	604 KB

cave

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

using namespace std;

#define lim 5005

int n,arr[lim],arr_use[lim];
bool kesin[lim];
int tut;

vector<int> deg;

inline void change(int l,int r,int val){
	int cur=0;
	deg.clear();
	for(int i=0;i<n;i++){
		if(kesin[i])continue;
		if(cur>=l && cur<=r){
			arr_use[i]=val;
			tut=i;
			deg.push_back(i);
		}
		cur++;
	}
}

inline void rechange(){
	for(auto ind:deg){
		arr_use[ind]=0;
	}
}

void exploreCave(int N) {
	n=N;
	int ans[n],ans2[n];
	
	for(int i=0;i<n;i++){
		int door=tryCombination(arr);
		if(door!=i)ans[i]=0; //cevap 0da
		else ans[i]=1; // cevap 1de
		int l=0,r=n-i-1;
		
		if(ans[i]){
			for(int i=0;i<n;i++){
				if(kesin[i])continue;
				arr_use[i]=1;
			}
		}
		
		while(l<=r){
			int m=(l+r)/2;
			change(l,m,ans[i]^1);
			int door_use=tryCombination(arr_use);
			rechange();
			if(door_use!=i){
				l=m+1;
				tut=m;
			}
			else r=m-1;
		}
		ans2[tut]=i;
		kesin[tut]=1;
		arr[tut]=ans[i];
		for(int i=0;i<n;i++){
			arr_use[i]=arr[i];
		}
		
	}
	
	int anss[n];
	
	for(int i=0;i<n;i++){
		anss[i]=ans[ans2[i]];
	}
	
	answer(anss,ans2);
	return ;
}

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	500 ms	536 KB	Output is correct
2	Correct	512 ms	568 KB	Output is correct
3	Correct	794 ms	572 KB	Output is correct
4	Correct	532 ms	556 KB	Output is correct
5	Correct	782 ms	560 KB	Output is correct
6	Correct	781 ms	596 KB	Output is correct
7	Correct	776 ms	576 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	779 ms	572 KB	Output is correct
13	Correct	776 ms	572 KB	Output is correct
14	Correct	779 ms	560 KB	Output is correct

Subtask #2

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	781 ms	564 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Incorrect	808 ms	560 KB	Answer is wrong
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Runtime error	1 ms	604 KB	Execution killed with signal 11
8	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Runtime error	1 ms	604 KB	Execution killed with signal 11
8	Halted	0 ms	0 KB	-

Subtask #5

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	500 ms	536 KB	Output is correct
2	Correct	512 ms	568 KB	Output is correct
3	Correct	794 ms	572 KB	Output is correct
4	Correct	532 ms	556 KB	Output is correct
5	Correct	782 ms	560 KB	Output is correct
6	Correct	781 ms	596 KB	Output is correct
7	Correct	776 ms	576 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	779 ms	572 KB	Output is correct
13	Correct	776 ms	572 KB	Output is correct
14	Correct	779 ms	560 KB	Output is correct
15	Correct	781 ms	564 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Incorrect	808 ms	560 KB	Answer is wrong
18	Halted	0 ms	0 KB	-