oj.uz

Submission #4476

# Submission time Handle Problem Language Result Execution time Memory
4476 2013-10-08T11:02:39 Z pichulia Cave (IOI13_cave) C++
51 / 100
 136 ms 664 KB 
#include "cave.h"
#include<stdio.h>

static int sw[5005];
static int de[5005];
void exploreCave(int N) {
	int i, j;
	int l, r, m;
	int s[5005];
	for(i=0; i<N;i++)
	{
		sw[i] = -1;
		s[i] = -1;
		de[i] = -1;
	}
	int result1;
	int result2;
	for(i=0; i<N; i++)
	{
		l=0;r=N-1;
		while(l<r)
		{
			m=(l+r)/2;
			for(j=l;j<=r;j++)
			{
				if(sw[j]==-1)
					s[j]=1;
				else
					s[j]=sw[j];
			}
			result1 = tryCombination(s);
			for(j=l;j<=m;j++)
			{
				if(sw[j]==-1)
					s[j]=0;
				else
					s[j]=sw[j];
			}
			result2 = tryCombination(s);

//			for(j=l;j<=r;j++)
//				printf("%d",s[j]);
//			printf("\n");
//			printf("%d %d %d, %d %d\n",l,m,r, result1,result2);

			if(result1 != i)
			{
				if(result2 == i)
				{
					r=m;
				}
				else
				{
					if(m==l)
						l=m+1;
					else
					l=m;
				}
			}
			else
			{
				if(result2==i)
				{
					if(m==l)
						l=m+1;
					else
					l=m;
				}
				else
				{
					r=m;
				}
			}
		}
	//	printf("%d\n",l);
		s[l] = 0;
		result1 = tryCombination(s); 
		s[l] = 1;
		result2 = tryCombination(s);
		if(result1 == i) sw[l] = 1;
		else sw[l] = 0;

		de[l] = i;
	}
	answer(sw, de);
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 384 KB too much calls on tryCombination()
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 664 KB too much calls on tryCombination()
2 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 ms 512 KB Output is correct
3 Correct 5 ms 520 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 392 KB Output is correct
9 Correct 5 ms 396 KB Output is correct
10 Correct 5 ms 456 KB Output is correct
11 Correct 6 ms 456 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 6 ms 512 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 396 KB Output is correct
6 Correct 91 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 75 ms 464 KB Output is correct
10 Correct 73 ms 468 KB Output is correct
11 Correct 71 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 72 ms 468 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 88 ms 384 KB Output is correct
17 Correct 74 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 6 ms 384 KB Output is correct
21 Correct 71 ms 472 KB Output is correct
22 Correct 60 ms 512 KB Output is correct
23 Correct 5 ms 464 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 456 KB too much calls on tryCombination()
2 Halted 0 ms 0 KB -