oj.uz

Submission #433787

# Submission time Handle Problem Language Result Execution time Memory
433787 2021-06-20T10:50:34 Z alishahali1382 Minerals (JOI19_minerals) C++14
40 / 100
 191 ms 6244 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;

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){
	// debugv(X)
	// debugv(Y)
	// cerr<<"\n";

	assert(SZ(X)==SZ(Y));
	if (SZ(X)==1){
		Answer(X[0], Y[0]);
		return ;
	}
	int sz=SZ(X), mid=sz/2;
	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 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 584 KB Output is correct
3 Correct 22 ms 840 KB Output is correct
4 Correct 40 ms 1564 KB Output is correct
5 Correct 86 ms 2572 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 584 KB Output is correct
7 Correct 22 ms 840 KB Output is correct
8 Correct 40 ms 1564 KB Output is correct
9 Correct 86 ms 2572 KB Output is correct
10 Correct 5 ms 420 KB Output is correct
11 Correct 56 ms 1912 KB Output is correct
12 Correct 85 ms 2652 KB Output is correct
13 Correct 78 ms 2664 KB Output is correct
14 Correct 81 ms 2524 KB Output is correct

Subtask #4
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 584 KB Output is correct
7 Correct 22 ms 840 KB Output is correct
8 Correct 40 ms 1564 KB Output is correct
9 Correct 86 ms 2572 KB Output is correct
10 Correct 5 ms 420 KB Output is correct
11 Correct 56 ms 1912 KB Output is correct
12 Correct 85 ms 2652 KB Output is correct
13 Correct 78 ms 2664 KB Output is correct
14 Correct 81 ms 2524 KB Output is correct
15 Incorrect 191 ms 6244 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #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 584 KB Output is correct
7 Correct 22 ms 840 KB Output is correct
8 Correct 40 ms 1564 KB Output is correct
9 Correct 86 ms 2572 KB Output is correct
10 Correct 5 ms 420 KB Output is correct
11 Correct 56 ms 1912 KB Output is correct
12 Correct 85 ms 2652 KB Output is correct
13 Correct 78 ms 2664 KB Output is correct
14 Correct 81 ms 2524 KB Output is correct
15 Incorrect 191 ms 6244 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
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 584 KB Output is correct
7 Correct 22 ms 840 KB Output is correct
8 Correct 40 ms 1564 KB Output is correct
9 Correct 86 ms 2572 KB Output is correct
10 Correct 5 ms 420 KB Output is correct
11 Correct 56 ms 1912 KB Output is correct
12 Correct 85 ms 2652 KB Output is correct
13 Correct 78 ms 2664 KB Output is correct
14 Correct 81 ms 2524 KB Output is correct
15 Incorrect 191 ms 6244 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
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 584 KB Output is correct
7 Correct 22 ms 840 KB Output is correct
8 Correct 40 ms 1564 KB Output is correct
9 Correct 86 ms 2572 KB Output is correct
10 Correct 5 ms 420 KB Output is correct
11 Correct 56 ms 1912 KB Output is correct
12 Correct 85 ms 2652 KB Output is correct
13 Correct 78 ms 2664 KB Output is correct
14 Correct 81 ms 2524 KB Output is correct
15 Incorrect 191 ms 6244 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
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 584 KB Output is correct
7 Correct 22 ms 840 KB Output is correct
8 Correct 40 ms 1564 KB Output is correct
9 Correct 86 ms 2572 KB Output is correct
10 Correct 5 ms 420 KB Output is correct
11 Correct 56 ms 1912 KB Output is correct
12 Correct 85 ms 2652 KB Output is correct
13 Correct 78 ms 2664 KB Output is correct
14 Correct 81 ms 2524 KB Output is correct
15 Incorrect 191 ms 6244 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

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 584 KB Output is correct
7 Correct 22 ms 840 KB Output is correct
8 Correct 40 ms 1564 KB Output is correct
9 Correct 86 ms 2572 KB Output is correct
10 Correct 5 ms 420 KB Output is correct
11 Correct 56 ms 1912 KB Output is correct
12 Correct 85 ms 2652 KB Output is correct
13 Correct 78 ms 2664 KB Output is correct
14 Correct 81 ms 2524 KB Output is correct
15 Incorrect 191 ms 6244 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -