oj.uz

Submission #433925

# Submission time Handle Problem Language Result Execution time Memory
433925 2021-06-20T12:18:26 Z alishahali1382 Minerals (JOI19_minerals) C++14
90 / 100
 588 ms 6968 KB 
#include "minerals.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) ((int)x.size())

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

int n, m, k, u, v, x, y, a, b, t, ans;
int mark[MAXN], shit;
set<int> On;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int Ask(int x){
	// cerr<<"Ask "<<x<<"\n";
	auto it=On.find(x);
	if (it==On.end()) On.insert(x);
	else On.erase(it);
	return ans=Query(x);
}
bool IsOn(int x){ return On.find(x)!=On.end();}
/*
void Set(vi vec){
	shit++;
	for (int x:vec){
		mark[x]=shit;
		if (!IsOn(x)) Ask(x);
	}
	vi rem;
	for (int x:On) if (mark[x]!=shit) rem.pb(x);
	for (int x:rem) Ask(x);
}*/

void divide(vi X, vi Y){
	assert(SZ(X)==SZ(Y));
	if (SZ(X)==1){
		Answer(X[0], Y[0]);
		return ;
	}
	int sz=SZ(X), mid=sz/2;
	// shuffle(all(X), rng);
	vi X1, X2, Y1, Y2;
	for (int i=0; i<sz; i++){
		if (i<mid) X1.pb(X[i]);
		else X2.pb(X[i]);
	}
	// Set(X1);
	for (int x:X1) if (!IsOn(x)) Ask(x);
	for (int x:X2) if (IsOn(x)) Ask(x);
	for (int y:Y) if (IsOn(x)) Ask(x);

	for (int y:Y){
		if (SZ(Y1)==mid) Y2.pb(y);
		else if (SZ(Y2)==sz-mid) Y1.pb(y);
		else{
			int last=ans;
			if (Ask(y)==last) Y1.pb(y);
			else Y2.pb(y);
		}
	}
	divide(X1, Y1);
	divide(X2, Y2);
}

void Solve(int _n){
	n=_n;
	vi X, Y, P(2*n);
	iota(all(P), 1);
	shuffle(all(P), rng);
	for (int i:P){
		int last=ans;
		if (SZ(X)==n || Ask(i)==last) Y.pb(i);
		else X.pb(i);
	}
	divide(X, Y);
}

Compilation message

minerals.cpp: In function 'void divide(vi, vi)':
minerals.cpp:67:11: warning: unused variable 'y' [-Wunused-variable]
   67 |  for (int y:Y) if (IsOn(x)) Ask(x);
      |           ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 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 5 ms 456 KB Output is correct
2 Correct 11 ms 608 KB Output is correct
3 Correct 24 ms 908 KB Output is correct
4 Correct 64 ms 1492 KB Output is correct
5 Correct 127 ms 2448 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 5 ms 456 KB Output is correct
6 Correct 11 ms 608 KB Output is correct
7 Correct 24 ms 908 KB Output is correct
8 Correct 64 ms 1492 KB Output is correct
9 Correct 127 ms 2448 KB Output is correct
10 Correct 5 ms 456 KB Output is correct
11 Correct 86 ms 1848 KB Output is correct
12 Correct 147 ms 2604 KB Output is correct
13 Correct 126 ms 2492 KB Output is correct
14 Correct 128 ms 2628 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 5 ms 456 KB Output is correct
6 Correct 11 ms 608 KB Output is correct
7 Correct 24 ms 908 KB Output is correct
8 Correct 64 ms 1492 KB Output is correct
9 Correct 127 ms 2448 KB Output is correct
10 Correct 5 ms 456 KB Output is correct
11 Correct 86 ms 1848 KB Output is correct
12 Correct 147 ms 2604 KB Output is correct
13 Correct 126 ms 2492 KB Output is correct
14 Correct 128 ms 2628 KB Output is correct
15 Correct 421 ms 6200 KB Output is correct
16 Correct 430 ms 6224 KB Output is correct
17 Correct 429 ms 6220 KB Output is correct
18 Correct 430 ms 6060 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 5 ms 456 KB Output is correct
6 Correct 11 ms 608 KB Output is correct
7 Correct 24 ms 908 KB Output is correct
8 Correct 64 ms 1492 KB Output is correct
9 Correct 127 ms 2448 KB Output is correct
10 Correct 5 ms 456 KB Output is correct
11 Correct 86 ms 1848 KB Output is correct
12 Correct 147 ms 2604 KB Output is correct
13 Correct 126 ms 2492 KB Output is correct
14 Correct 128 ms 2628 KB Output is correct
15 Correct 421 ms 6200 KB Output is correct
16 Correct 430 ms 6224 KB Output is correct
17 Correct 429 ms 6220 KB Output is correct
18 Correct 430 ms 6060 KB Output is correct
19 Correct 429 ms 6336 KB Output is correct
20 Correct 474 ms 6404 KB Output is correct
21 Correct 419 ms 6396 KB Output is correct
22 Correct 448 ms 6196 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 5 ms 456 KB Output is correct
6 Correct 11 ms 608 KB Output is correct
7 Correct 24 ms 908 KB Output is correct
8 Correct 64 ms 1492 KB Output is correct
9 Correct 127 ms 2448 KB Output is correct
10 Correct 5 ms 456 KB Output is correct
11 Correct 86 ms 1848 KB Output is correct
12 Correct 147 ms 2604 KB Output is correct
13 Correct 126 ms 2492 KB Output is correct
14 Correct 128 ms 2628 KB Output is correct
15 Correct 421 ms 6200 KB Output is correct
16 Correct 430 ms 6224 KB Output is correct
17 Correct 429 ms 6220 KB Output is correct
18 Correct 430 ms 6060 KB Output is correct
19 Correct 429 ms 6336 KB Output is correct
20 Correct 474 ms 6404 KB Output is correct
21 Correct 419 ms 6396 KB Output is correct
22 Correct 448 ms 6196 KB Output is correct
23 Correct 479 ms 6540 KB Output is correct
24 Correct 455 ms 6488 KB Output is correct
25 Correct 452 ms 6540 KB Output is correct
26 Correct 440 ms 6404 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 5 ms 456 KB Output is correct
6 Correct 11 ms 608 KB Output is correct
7 Correct 24 ms 908 KB Output is correct
8 Correct 64 ms 1492 KB Output is correct
9 Correct 127 ms 2448 KB Output is correct
10 Correct 5 ms 456 KB Output is correct
11 Correct 86 ms 1848 KB Output is correct
12 Correct 147 ms 2604 KB Output is correct
13 Correct 126 ms 2492 KB Output is correct
14 Correct 128 ms 2628 KB Output is correct
15 Correct 421 ms 6200 KB Output is correct
16 Correct 430 ms 6224 KB Output is correct
17 Correct 429 ms 6220 KB Output is correct
18 Correct 430 ms 6060 KB Output is correct
19 Correct 429 ms 6336 KB Output is correct
20 Correct 474 ms 6404 KB Output is correct
21 Correct 419 ms 6396 KB Output is correct
22 Correct 448 ms 6196 KB Output is correct
23 Correct 479 ms 6540 KB Output is correct
24 Correct 455 ms 6488 KB Output is correct
25 Correct 452 ms 6540 KB Output is correct
26 Correct 440 ms 6404 KB Output is correct
27 Correct 462 ms 6700 KB Output is correct
28 Correct 482 ms 6700 KB Output is correct
29 Correct 442 ms 6708 KB Output is correct
30 Correct 497 ms 6476 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 5 ms 456 KB Output is correct
6 Correct 11 ms 608 KB Output is correct
7 Correct 24 ms 908 KB Output is correct
8 Correct 64 ms 1492 KB Output is correct
9 Correct 127 ms 2448 KB Output is correct
10 Correct 5 ms 456 KB Output is correct
11 Correct 86 ms 1848 KB Output is correct
12 Correct 147 ms 2604 KB Output is correct
13 Correct 126 ms 2492 KB Output is correct
14 Correct 128 ms 2628 KB Output is correct
15 Correct 421 ms 6200 KB Output is correct
16 Correct 430 ms 6224 KB Output is correct
17 Correct 429 ms 6220 KB Output is correct
18 Correct 430 ms 6060 KB Output is correct
19 Correct 429 ms 6336 KB Output is correct
20 Correct 474 ms 6404 KB Output is correct
21 Correct 419 ms 6396 KB Output is correct
22 Correct 448 ms 6196 KB Output is correct
23 Correct 479 ms 6540 KB Output is correct
24 Correct 455 ms 6488 KB Output is correct
25 Correct 452 ms 6540 KB Output is correct
26 Correct 440 ms 6404 KB Output is correct
27 Correct 462 ms 6700 KB Output is correct
28 Correct 482 ms 6700 KB Output is correct
29 Correct 442 ms 6708 KB Output is correct
30 Correct 497 ms 6476 KB Output is correct
31 Correct 488 ms 6872 KB Output is correct
32 Correct 486 ms 6844 KB Output is correct
33 Correct 502 ms 6860 KB Output is correct
34 Correct 545 ms 6732 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 5 ms 456 KB Output is correct
6 Correct 11 ms 608 KB Output is correct
7 Correct 24 ms 908 KB Output is correct
8 Correct 64 ms 1492 KB Output is correct
9 Correct 127 ms 2448 KB Output is correct
10 Correct 5 ms 456 KB Output is correct
11 Correct 86 ms 1848 KB Output is correct
12 Correct 147 ms 2604 KB Output is correct
13 Correct 126 ms 2492 KB Output is correct
14 Correct 128 ms 2628 KB Output is correct
15 Correct 421 ms 6200 KB Output is correct
16 Correct 430 ms 6224 KB Output is correct
17 Correct 429 ms 6220 KB Output is correct
18 Correct 430 ms 6060 KB Output is correct
19 Correct 429 ms 6336 KB Output is correct
20 Correct 474 ms 6404 KB Output is correct
21 Correct 419 ms 6396 KB Output is correct
22 Correct 448 ms 6196 KB Output is correct
23 Correct 479 ms 6540 KB Output is correct
24 Correct 455 ms 6488 KB Output is correct
25 Correct 452 ms 6540 KB Output is correct
26 Correct 440 ms 6404 KB Output is correct
27 Correct 462 ms 6700 KB Output is correct
28 Correct 482 ms 6700 KB Output is correct
29 Correct 442 ms 6708 KB Output is correct
30 Correct 497 ms 6476 KB Output is correct
31 Correct 488 ms 6872 KB Output is correct
32 Correct 486 ms 6844 KB Output is correct
33 Correct 502 ms 6860 KB Output is correct
34 Correct 545 ms 6732 KB Output is correct
35 Incorrect 588 ms 6968 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -