oj.uz

Submission #318785

# Submission time Handle Problem Language Result Execution time Memory
318785 2020-11-03T08:24:34 Z Foxyy Cave (IOI13_cave) C++14
25 / 100
 799 ms 516 KB 
#include "cave.h"

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

const int MAXN = 200000;
const int INF = 0x3f3f3f3f, MOD = 1000000007;
#define INIT(arr, val) fill(arr, arr+(int)(sizeof(arr)/sizeof(arr[0])), val)
#define REP(i, lb, rb, inc) for(int i = (lb); i < (rb); i += inc)
#define RREP(i, rb, lb, dec) for(int i = (rb)-1; i >= (lb); i -= dec)
typedef long long ll;
#define sz size()
typedef stack<int, vector<int> > SI;
typedef queue<int> QI;
typedef vector<int> VI;
#define pb push_back
typedef pair<int, int> PII;
#define mp make_pair
#define F first
#define S second
#define endl '\n'
#define dbg(a, b) cerr << "dbg: a " << b << endl;
#define dbg_itv(a, b, c) cerr << "dbg_itv: " << a << " " << b << " : " << c << endl
#define IOS() cin.tie(0); cout.sync_with_stdio(0)

void exploreCave(int N) {
	int arr[N];
	PII ans[N];
    REP(i, 0, N, 1) {
    	fill(arr, arr+N, 0);
    	REP(j, 0, i, 1) arr[ans[j].F] = ans[j].S;
    	int ret = tryCombination(arr);
   		if (ret > i || ret == -1) ans[i].S = 0;
		else		 ans[i].S = 1;
		int lb, rb;
		lb = 0; rb  = N;
		while(rb - lb - 1 > 0) {
			int mid = (lb+rb)/2;
			fill(arr+lb, arr+mid, ans[i].S); fill(arr+mid, arr+rb, 1-ans[i].S);
    		REP(j, 0, i, 1) arr[ans[j].F] = ans[j].S;
			ret = tryCombination(arr);
			if (ret > i || ret == -1) rb = mid;
			else		 lb = mid;
		}
		ans[i].F = lb;
	}
	int s[N], d[N];
	REP(i, 0, N, 1) {
		d[ans[i].F] = i;
		s[i] = ans[i].S;
	}
	answer(s, d);
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 484 KB Output is correct
2 Correct 460 ms 484 KB Output is correct
3 Correct 727 ms 484 KB Output is correct
4 Correct 488 ms 484 KB Output is correct
5 Correct 738 ms 484 KB Output is correct
6 Correct 721 ms 484 KB Output is correct
7 Correct 744 ms 484 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 718 ms 484 KB Output is correct
13 Correct 717 ms 484 KB Output is correct
14 Correct 720 ms 484 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 480 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 751 ms 484 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 736 ms 484 KB Output is correct
7 Correct 798 ms 472 KB Output is correct
8 Correct 784 ms 480 KB Output is correct
9 Correct 785 ms 516 KB Output is correct
10 Correct 782 ms 484 KB Output is correct
11 Correct 799 ms 484 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Answer is wrong
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Answer is wrong
6 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 484 KB Output is correct
2 Correct 460 ms 484 KB Output is correct
3 Correct 727 ms 484 KB Output is correct
4 Correct 488 ms 484 KB Output is correct
5 Correct 738 ms 484 KB Output is correct
6 Correct 721 ms 484 KB Output is correct
7 Correct 744 ms 484 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 718 ms 484 KB Output is correct
13 Correct 717 ms 484 KB Output is correct
14 Correct 720 ms 484 KB Output is correct
15 Correct 740 ms 480 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 751 ms 484 KB Output is correct
18 Correct 0 ms 364 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Correct 736 ms 484 KB Output is correct
21 Correct 798 ms 472 KB Output is correct
22 Correct 784 ms 480 KB Output is correct
23 Correct 785 ms 516 KB Output is correct
24 Correct 782 ms 484 KB Output is correct
25 Correct 799 ms 484 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 0 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 0 ms 364 KB Output is correct
30 Incorrect 1 ms 364 KB Answer is wrong
31 Halted 0 ms 0 KB -