oj.uz

Submission #494873

# Submission time Handle Problem Language Result Execution time Memory
494873 2021-12-17T03:44:23 Z flappybird Minerals (JOI19_minerals) C++14
85 / 100
 97 ms 8992 KB 
#include "minerals.h"
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
typedef long long ll;
#define ln '\n'
#define MAX 101010
#define C 0.618

ll rnd[MAX];
vector<ll> A, B; //A is old
ll chk[MAX];
ll ans[MAX];
ll rem[MAX];
ll num[MAX];
ll pass[MAX];
ll pv = 0;
ll pvv = 0;

ll query(ll x) {
	rem[x] = !rem[x];
	pv = pvv;
	pvv = Query(rnd[x]);
	return pvv;
}

void answer(ll x, ll y) {
	Answer(rnd[x], rnd[y]);
}

void dnc(vector<ll> v1, vector<ll> v2, bool c = false) {
	ll N = v1.size();
	if (N == 1) {
		ans[v1[0]] = v2[0];
		return;
	}
	if (N == 2) {
		if (!rem[B[v2[0]]] || !rem[B[v2[0]]]) query(B[v2[0]]);
		if (rem[B[v2[0]]]) {
			if (rem[B[v2[1]]]) query(B[v2[1]]);
			ans[v1[0]] = v2[0];
			ans[v1[1]] = v2[1];
			if (query(A[v1[0]]) != pv) swap(ans[v1[0]], ans[v1[1]]);
		}
		else {
			ans[v1[0]] = v2[1];
			ans[v1[1]] = v2[0];
			if (query(A[v1[0]]) != pv) swap(ans[v1[0]], ans[v1[1]]);
		}
		return;
	}
	ll i;
	vector<ll> in, out;
	for (i = 0; i < N; i++) (rem[B[v2[i]]] ? in : out).push_back(v2[i]);
	ll sz = N * C;
	if (abs(sz - (ll)in.size()) > abs(N * (1. - C) - (ll)in.size())) sz = N * (1. - C);
	while (in.size() < sz) {
		ll a = out.back();
		out.pop_back();
		query(B[a]);
		in.push_back(a);
	}
	while (in.size() > sz) {
		ll a = in.back();
		in.pop_back();
		query(B[a]);
		out.push_back(a);
	}
	vector<ll> in1, out1;
	for (i = 0; i < N; i++) {
		if (c && pass[i]) in1.push_back(v1[i]);
		else {
			if (pv == query(A[v1[i]])) in1.push_back(v1[i]);
			else out1.push_back(v1[i]);
		}
	}
	dnc(in1, in);
	dnc(out1, out);
}

void rnd_gen(ll N) {
	//mt19937 engine((unsigned int)time(NULL));
	//uniform_int_distribution<int> distribution(0, 1000000000);
	//auto generator = bind(distribution, engine);
	ll i;
	ll j;
	for (i = 1; i <= 2 * N; i++) rnd[i] = i;
	for (j = 0; j < 2; j++) {
		for (i = 2 * N; i > 1; i--) {
			ll a = rand() % i + 1;
			swap(rnd[i], rnd[a]);
		}
	}
}

ll anschk[MAX];
ll checked[MAX];

void Solve(int N) {
	mt19937 engine((unsigned int)time(NULL));
	uniform_int_distribution<int> distribution(0, 1000000000);
	auto generator = bind(distribution, engine);
	ll i;
	rnd_gen(N);
	for (i = 1; i <= 2 * N; i++) {
		ll res = query(i);
		if (res != pv) {
			B.push_back(i);
			chk[i] = 1;
		}
		else {
			A.push_back(i);
			num[A.size() - 1] = B.size();
			chk[i] = 0;
		}
	}
	for (i = 0; i < N; i++) if (num[i] <= N * C) pass[i] = 1;
	vector<ll> v;
	for (i = 0; i < N; i++) v.push_back(i);
	dnc(v, v, 1);
	for (i = 0; i < N; i++) answer(A[i], B[ans[i]]);
}

Compilation message

minerals.cpp: In function 'void dnc(std::vector<long long int>, std::vector<long long int>, bool)':
minerals.cpp:57:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   57 |  while (in.size() < sz) {
      |         ~~~~~~~~~~^~~~
minerals.cpp:63:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   63 |  while (in.size() > sz) {
      |         ~~~~~~~~~~^~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:102:7: warning: variable 'generator' set but not used [-Wunused-but-set-variable]
  102 |  auto generator = bind(distribution, engine);
      |       ^~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 456 KB Output is correct
2 Correct 3 ms 712 KB Output is correct
3 Correct 6 ms 1196 KB Output is correct
4 Correct 11 ms 2012 KB Output is correct
5 Correct 23 ms 3400 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 3 ms 712 KB Output is correct
7 Correct 6 ms 1196 KB Output is correct
8 Correct 11 ms 2012 KB Output is correct
9 Correct 23 ms 3400 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 16 ms 2492 KB Output is correct
12 Correct 27 ms 3556 KB Output is correct
13 Correct 26 ms 3504 KB Output is correct
14 Correct 31 ms 3528 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 3 ms 712 KB Output is correct
7 Correct 6 ms 1196 KB Output is correct
8 Correct 11 ms 2012 KB Output is correct
9 Correct 23 ms 3400 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 16 ms 2492 KB Output is correct
12 Correct 27 ms 3556 KB Output is correct
13 Correct 26 ms 3504 KB Output is correct
14 Correct 31 ms 3528 KB Output is correct
15 Correct 84 ms 8392 KB Output is correct
16 Correct 66 ms 8460 KB Output is correct
17 Correct 97 ms 8372 KB Output is correct
18 Correct 69 ms 8196 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 3 ms 712 KB Output is correct
7 Correct 6 ms 1196 KB Output is correct
8 Correct 11 ms 2012 KB Output is correct
9 Correct 23 ms 3400 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 16 ms 2492 KB Output is correct
12 Correct 27 ms 3556 KB Output is correct
13 Correct 26 ms 3504 KB Output is correct
14 Correct 31 ms 3528 KB Output is correct
15 Correct 84 ms 8392 KB Output is correct
16 Correct 66 ms 8460 KB Output is correct
17 Correct 97 ms 8372 KB Output is correct
18 Correct 69 ms 8196 KB Output is correct
19 Correct 71 ms 8516 KB Output is correct
20 Correct 68 ms 8516 KB Output is correct
21 Correct 73 ms 8676 KB Output is correct
22 Correct 77 ms 8412 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 3 ms 712 KB Output is correct
7 Correct 6 ms 1196 KB Output is correct
8 Correct 11 ms 2012 KB Output is correct
9 Correct 23 ms 3400 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 16 ms 2492 KB Output is correct
12 Correct 27 ms 3556 KB Output is correct
13 Correct 26 ms 3504 KB Output is correct
14 Correct 31 ms 3528 KB Output is correct
15 Correct 84 ms 8392 KB Output is correct
16 Correct 66 ms 8460 KB Output is correct
17 Correct 97 ms 8372 KB Output is correct
18 Correct 69 ms 8196 KB Output is correct
19 Correct 71 ms 8516 KB Output is correct
20 Correct 68 ms 8516 KB Output is correct
21 Correct 73 ms 8676 KB Output is correct
22 Correct 77 ms 8412 KB Output is correct
23 Correct 71 ms 8644 KB Output is correct
24 Correct 79 ms 8684 KB Output is correct
25 Correct 76 ms 8712 KB Output is correct
26 Correct 87 ms 8576 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 3 ms 712 KB Output is correct
7 Correct 6 ms 1196 KB Output is correct
8 Correct 11 ms 2012 KB Output is correct
9 Correct 23 ms 3400 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 16 ms 2492 KB Output is correct
12 Correct 27 ms 3556 KB Output is correct
13 Correct 26 ms 3504 KB Output is correct
14 Correct 31 ms 3528 KB Output is correct
15 Correct 84 ms 8392 KB Output is correct
16 Correct 66 ms 8460 KB Output is correct
17 Correct 97 ms 8372 KB Output is correct
18 Correct 69 ms 8196 KB Output is correct
19 Correct 71 ms 8516 KB Output is correct
20 Correct 68 ms 8516 KB Output is correct
21 Correct 73 ms 8676 KB Output is correct
22 Correct 77 ms 8412 KB Output is correct
23 Correct 71 ms 8644 KB Output is correct
24 Correct 79 ms 8684 KB Output is correct
25 Correct 76 ms 8712 KB Output is correct
26 Correct 87 ms 8576 KB Output is correct
27 Correct 74 ms 8908 KB Output is correct
28 Correct 88 ms 8916 KB Output is correct
29 Correct 92 ms 8980 KB Output is correct
30 Correct 74 ms 8748 KB Output is correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 3 ms 712 KB Output is correct
7 Correct 6 ms 1196 KB Output is correct
8 Correct 11 ms 2012 KB Output is correct
9 Correct 23 ms 3400 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 16 ms 2492 KB Output is correct
12 Correct 27 ms 3556 KB Output is correct
13 Correct 26 ms 3504 KB Output is correct
14 Correct 31 ms 3528 KB Output is correct
15 Correct 84 ms 8392 KB Output is correct
16 Correct 66 ms 8460 KB Output is correct
17 Correct 97 ms 8372 KB Output is correct
18 Correct 69 ms 8196 KB Output is correct
19 Correct 71 ms 8516 KB Output is correct
20 Correct 68 ms 8516 KB Output is correct
21 Correct 73 ms 8676 KB Output is correct
22 Correct 77 ms 8412 KB Output is correct
23 Correct 71 ms 8644 KB Output is correct
24 Correct 79 ms 8684 KB Output is correct
25 Correct 76 ms 8712 KB Output is correct
26 Correct 87 ms 8576 KB Output is correct
27 Correct 74 ms 8908 KB Output is correct
28 Correct 88 ms 8916 KB Output is correct
29 Correct 92 ms 8980 KB Output is correct
30 Correct 74 ms 8748 KB Output is correct
31 Incorrect 83 ms 8992 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 3 ms 712 KB Output is correct
7 Correct 6 ms 1196 KB Output is correct
8 Correct 11 ms 2012 KB Output is correct
9 Correct 23 ms 3400 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 16 ms 2492 KB Output is correct
12 Correct 27 ms 3556 KB Output is correct
13 Correct 26 ms 3504 KB Output is correct
14 Correct 31 ms 3528 KB Output is correct
15 Correct 84 ms 8392 KB Output is correct
16 Correct 66 ms 8460 KB Output is correct
17 Correct 97 ms 8372 KB Output is correct
18 Correct 69 ms 8196 KB Output is correct
19 Correct 71 ms 8516 KB Output is correct
20 Correct 68 ms 8516 KB Output is correct
21 Correct 73 ms 8676 KB Output is correct
22 Correct 77 ms 8412 KB Output is correct
23 Correct 71 ms 8644 KB Output is correct
24 Correct 79 ms 8684 KB Output is correct
25 Correct 76 ms 8712 KB Output is correct
26 Correct 87 ms 8576 KB Output is correct
27 Correct 74 ms 8908 KB Output is correct
28 Correct 88 ms 8916 KB Output is correct
29 Correct 92 ms 8980 KB Output is correct
30 Correct 74 ms 8748 KB Output is correct
31 Incorrect 83 ms 8992 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -