oj.uz

Submission #433932

# Submission time Handle Problem Language Result Execution time Memory
433932 2021-06-20T12:22:07 Z alishahali1382 Minerals (JOI19_minerals) C++14
90 / 100
 568 ms 7400 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 ;
	}
	if (rng()&1) swap(X, Y);
	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:68:11: warning: unused variable 'y' [-Wunused-variable]
   68 |  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 6 ms 584 KB Output is correct
2 Correct 13 ms 616 KB Output is correct
3 Correct 31 ms 940 KB Output is correct
4 Correct 59 ms 1500 KB Output is correct
5 Correct 139 ms 2716 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 6 ms 584 KB Output is correct
6 Correct 13 ms 616 KB Output is correct
7 Correct 31 ms 940 KB Output is correct
8 Correct 59 ms 1500 KB Output is correct
9 Correct 139 ms 2716 KB Output is correct
10 Correct 6 ms 456 KB Output is correct
11 Correct 81 ms 1864 KB Output is correct
12 Correct 132 ms 2556 KB Output is correct
13 Correct 154 ms 2572 KB Output is correct
14 Correct 134 ms 2544 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 6 ms 584 KB Output is correct
6 Correct 13 ms 616 KB Output is correct
7 Correct 31 ms 940 KB Output is correct
8 Correct 59 ms 1500 KB Output is correct
9 Correct 139 ms 2716 KB Output is correct
10 Correct 6 ms 456 KB Output is correct
11 Correct 81 ms 1864 KB Output is correct
12 Correct 132 ms 2556 KB Output is correct
13 Correct 154 ms 2572 KB Output is correct
14 Correct 134 ms 2544 KB Output is correct
15 Correct 449 ms 6740 KB Output is correct
16 Correct 443 ms 6324 KB Output is correct
17 Correct 421 ms 6756 KB Output is correct
18 Correct 513 ms 6092 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 6 ms 584 KB Output is correct
6 Correct 13 ms 616 KB Output is correct
7 Correct 31 ms 940 KB Output is correct
8 Correct 59 ms 1500 KB Output is correct
9 Correct 139 ms 2716 KB Output is correct
10 Correct 6 ms 456 KB Output is correct
11 Correct 81 ms 1864 KB Output is correct
12 Correct 132 ms 2556 KB Output is correct
13 Correct 154 ms 2572 KB Output is correct
14 Correct 134 ms 2544 KB Output is correct
15 Correct 449 ms 6740 KB Output is correct
16 Correct 443 ms 6324 KB Output is correct
17 Correct 421 ms 6756 KB Output is correct
18 Correct 513 ms 6092 KB Output is correct
19 Correct 481 ms 6740 KB Output is correct
20 Correct 455 ms 6296 KB Output is correct
21 Correct 450 ms 6376 KB Output is correct
22 Correct 460 ms 6588 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 6 ms 584 KB Output is correct
6 Correct 13 ms 616 KB Output is correct
7 Correct 31 ms 940 KB Output is correct
8 Correct 59 ms 1500 KB Output is correct
9 Correct 139 ms 2716 KB Output is correct
10 Correct 6 ms 456 KB Output is correct
11 Correct 81 ms 1864 KB Output is correct
12 Correct 132 ms 2556 KB Output is correct
13 Correct 154 ms 2572 KB Output is correct
14 Correct 134 ms 2544 KB Output is correct
15 Correct 449 ms 6740 KB Output is correct
16 Correct 443 ms 6324 KB Output is correct
17 Correct 421 ms 6756 KB Output is correct
18 Correct 513 ms 6092 KB Output is correct
19 Correct 481 ms 6740 KB Output is correct
20 Correct 455 ms 6296 KB Output is correct
21 Correct 450 ms 6376 KB Output is correct
22 Correct 460 ms 6588 KB Output is correct
23 Correct 481 ms 6540 KB Output is correct
24 Correct 461 ms 6520 KB Output is correct
25 Correct 496 ms 7016 KB Output is correct
26 Correct 475 ms 6752 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 6 ms 584 KB Output is correct
6 Correct 13 ms 616 KB Output is correct
7 Correct 31 ms 940 KB Output is correct
8 Correct 59 ms 1500 KB Output is correct
9 Correct 139 ms 2716 KB Output is correct
10 Correct 6 ms 456 KB Output is correct
11 Correct 81 ms 1864 KB Output is correct
12 Correct 132 ms 2556 KB Output is correct
13 Correct 154 ms 2572 KB Output is correct
14 Correct 134 ms 2544 KB Output is correct
15 Correct 449 ms 6740 KB Output is correct
16 Correct 443 ms 6324 KB Output is correct
17 Correct 421 ms 6756 KB Output is correct
18 Correct 513 ms 6092 KB Output is correct
19 Correct 481 ms 6740 KB Output is correct
20 Correct 455 ms 6296 KB Output is correct
21 Correct 450 ms 6376 KB Output is correct
22 Correct 460 ms 6588 KB Output is correct
23 Correct 481 ms 6540 KB Output is correct
24 Correct 461 ms 6520 KB Output is correct
25 Correct 496 ms 7016 KB Output is correct
26 Correct 475 ms 6752 KB Output is correct
27 Correct 447 ms 6752 KB Output is correct
28 Correct 475 ms 6684 KB Output is correct
29 Correct 476 ms 7236 KB Output is correct
30 Correct 476 ms 6540 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 6 ms 584 KB Output is correct
6 Correct 13 ms 616 KB Output is correct
7 Correct 31 ms 940 KB Output is correct
8 Correct 59 ms 1500 KB Output is correct
9 Correct 139 ms 2716 KB Output is correct
10 Correct 6 ms 456 KB Output is correct
11 Correct 81 ms 1864 KB Output is correct
12 Correct 132 ms 2556 KB Output is correct
13 Correct 154 ms 2572 KB Output is correct
14 Correct 134 ms 2544 KB Output is correct
15 Correct 449 ms 6740 KB Output is correct
16 Correct 443 ms 6324 KB Output is correct
17 Correct 421 ms 6756 KB Output is correct
18 Correct 513 ms 6092 KB Output is correct
19 Correct 481 ms 6740 KB Output is correct
20 Correct 455 ms 6296 KB Output is correct
21 Correct 450 ms 6376 KB Output is correct
22 Correct 460 ms 6588 KB Output is correct
23 Correct 481 ms 6540 KB Output is correct
24 Correct 461 ms 6520 KB Output is correct
25 Correct 496 ms 7016 KB Output is correct
26 Correct 475 ms 6752 KB Output is correct
27 Correct 447 ms 6752 KB Output is correct
28 Correct 475 ms 6684 KB Output is correct
29 Correct 476 ms 7236 KB Output is correct
30 Correct 476 ms 6540 KB Output is correct
31 Correct 503 ms 7280 KB Output is correct
32 Correct 523 ms 6888 KB Output is correct
33 Correct 466 ms 6832 KB Output is correct
34 Correct 530 ms 7092 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 6 ms 584 KB Output is correct
6 Correct 13 ms 616 KB Output is correct
7 Correct 31 ms 940 KB Output is correct
8 Correct 59 ms 1500 KB Output is correct
9 Correct 139 ms 2716 KB Output is correct
10 Correct 6 ms 456 KB Output is correct
11 Correct 81 ms 1864 KB Output is correct
12 Correct 132 ms 2556 KB Output is correct
13 Correct 154 ms 2572 KB Output is correct
14 Correct 134 ms 2544 KB Output is correct
15 Correct 449 ms 6740 KB Output is correct
16 Correct 443 ms 6324 KB Output is correct
17 Correct 421 ms 6756 KB Output is correct
18 Correct 513 ms 6092 KB Output is correct
19 Correct 481 ms 6740 KB Output is correct
20 Correct 455 ms 6296 KB Output is correct
21 Correct 450 ms 6376 KB Output is correct
22 Correct 460 ms 6588 KB Output is correct
23 Correct 481 ms 6540 KB Output is correct
24 Correct 461 ms 6520 KB Output is correct
25 Correct 496 ms 7016 KB Output is correct
26 Correct 475 ms 6752 KB Output is correct
27 Correct 447 ms 6752 KB Output is correct
28 Correct 475 ms 6684 KB Output is correct
29 Correct 476 ms 7236 KB Output is correct
30 Correct 476 ms 6540 KB Output is correct
31 Correct 503 ms 7280 KB Output is correct
32 Correct 523 ms 6888 KB Output is correct
33 Correct 466 ms 6832 KB Output is correct
34 Correct 530 ms 7092 KB Output is correct
35 Incorrect 568 ms 7400 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -