oj.uz

Submission #433790

# Submission time Handle Problem Language Result Execution time Memory
433790 2021-06-20T10:52:08 Z alishahali1382 Minerals (JOI19_minerals) C++14
40 / 100
 219 ms 6824 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);
	// debugv(On)
	for (int y:Y){
		int last=ans;
		if (Ask(y)==last) Y1.pb(y);
		else Y2.pb(y);
	}
	// debugv(X1)
	// debugv(X2)
	// debugv(Y1)
	// debugv(Y2)
	// cerr<<"\n\n";

	divide(X1, Y1);
	divide(X2, Y2);
}

void Solve(int _n){
	n=_n;
	vi X, Y;
	for (int i=1; i<=2*n; i++){
		int last=ans;
		if (Ask(i)==last) Y.pb(i);
		else X.pb(i);
	}
	divide(X, Y);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 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 10 ms 640 KB Output is correct
3 Correct 22 ms 960 KB Output is correct
4 Correct 47 ms 1480 KB Output is correct
5 Correct 108 ms 2632 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 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 10 ms 640 KB Output is correct
7 Correct 22 ms 960 KB Output is correct
8 Correct 47 ms 1480 KB Output is correct
9 Correct 108 ms 2632 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 84 ms 2064 KB Output is correct
12 Correct 109 ms 2900 KB Output is correct
13 Correct 109 ms 2928 KB Output is correct
14 Correct 97 ms 2616 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 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 10 ms 640 KB Output is correct
7 Correct 22 ms 960 KB Output is correct
8 Correct 47 ms 1480 KB Output is correct
9 Correct 108 ms 2632 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 84 ms 2064 KB Output is correct
12 Correct 109 ms 2900 KB Output is correct
13 Correct 109 ms 2928 KB Output is correct
14 Correct 97 ms 2616 KB Output is correct
15 Incorrect 219 ms 6824 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 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 10 ms 640 KB Output is correct
7 Correct 22 ms 960 KB Output is correct
8 Correct 47 ms 1480 KB Output is correct
9 Correct 108 ms 2632 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 84 ms 2064 KB Output is correct
12 Correct 109 ms 2900 KB Output is correct
13 Correct 109 ms 2928 KB Output is correct
14 Correct 97 ms 2616 KB Output is correct
15 Incorrect 219 ms 6824 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 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 10 ms 640 KB Output is correct
7 Correct 22 ms 960 KB Output is correct
8 Correct 47 ms 1480 KB Output is correct
9 Correct 108 ms 2632 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 84 ms 2064 KB Output is correct
12 Correct 109 ms 2900 KB Output is correct
13 Correct 109 ms 2928 KB Output is correct
14 Correct 97 ms 2616 KB Output is correct
15 Incorrect 219 ms 6824 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 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 10 ms 640 KB Output is correct
7 Correct 22 ms 960 KB Output is correct
8 Correct 47 ms 1480 KB Output is correct
9 Correct 108 ms 2632 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 84 ms 2064 KB Output is correct
12 Correct 109 ms 2900 KB Output is correct
13 Correct 109 ms 2928 KB Output is correct
14 Correct 97 ms 2616 KB Output is correct
15 Incorrect 219 ms 6824 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 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 10 ms 640 KB Output is correct
7 Correct 22 ms 960 KB Output is correct
8 Correct 47 ms 1480 KB Output is correct
9 Correct 108 ms 2632 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 84 ms 2064 KB Output is correct
12 Correct 109 ms 2900 KB Output is correct
13 Correct 109 ms 2928 KB Output is correct
14 Correct 97 ms 2616 KB Output is correct
15 Incorrect 219 ms 6824 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 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 10 ms 640 KB Output is correct
7 Correct 22 ms 960 KB Output is correct
8 Correct 47 ms 1480 KB Output is correct
9 Correct 108 ms 2632 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 84 ms 2064 KB Output is correct
12 Correct 109 ms 2900 KB Output is correct
13 Correct 109 ms 2928 KB Output is correct
14 Correct 97 ms 2616 KB Output is correct
15 Incorrect 219 ms 6824 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -