oj.uz

Submission #706213

# Submission time Handle Problem Language Result Execution time Memory
706213 2023-03-06T05:00:25 Z alvingogo Minerals (JOI19_minerals) C++14
6 / 100
 39 ms 6344 KB 
#include <bits/stdc++.h>
#include "minerals.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

/* Mineral:
i can only figure out that merge sort might be a useful idea

but it is 3/2 * n * log(n) = 1.5 * 43000 * 15 = 2.25 * 43000 = oh wow, i can't math

so the first thing is to find out n minerals which satisfies that no two minerals share the same type

which can be done in n steps

after that, we can merge sort it
let the two parts be X, Y, both have size n
1. put the first n/2 numbers in x to set
2. put every numbers in Y to set, check the answer being changed
3. for every numbers in Y which not causes the answer changed, pop out it from the set
4. go to the next two parts
it's 2*n?
no, for the next level, for one part we can see it as we have done the first step to Y
and for another we just think it the same

so let's go!!

3/2 * 43000 * 15 = 967500
1031500


the recursive function might code in this way:
f(X,Y,flag)
which flag = 0 -> we should do the first step
flag = 1 -> we shouldn't do

and oh, to find out if the correspond is in the first step 
we can check if Query() is same to the original answer

done!

*/


vector<int> dp;
int ans=0;

mt19937 rnd(time(NULL));
void f(vector<int>& x,vector<int>& y,int flag){
	int n=x.size();
	shuffle(x.begin(),x.end(),rnd);
	shuffle(y.begin(),y.end(),rnd);
	if(n==1){
		Answer(x[0],y[0]);
		return;
	}
	vector<int> a,b,c,d;
	int w=__lg(n-1);
	int p=dp[n],q=n-p;
	for(int i=0;i<p;i++){
		ans=Query(x[i]);
	}
	for(int i=0;i<p;i++){
		a.push_back(x[i]);
	}
	for(int i=p;i<n;i++){
		b.push_back(x[i]);
	}
	for(int i=0;i<n;i++){
		if(p==0){
			q--;
			d.push_back(y[i]);
			continue;
		}
		if(q==0){
			p--;
			c.push_back(y[i]);
			continue;
		}
		int e=Query(y[i]);
		if((e==ans) xor flag){
			c.push_back(y[i]);
			p--;
		}
		else{
			d.push_back(y[i]);
			q--;
		}
		ans=e;
	}
	f(a,c,flag^1);
	f(b,d,flag);
}
void Solve(int n){
	dp.resize(n+1);
	dp[0]=0;
	dp[1]=0;
	for(int i=2;i<=n;i++){
		dp[i]=1e9;
		for(int j=1;j<=i/2;j++){
			dp[i]=min(dp[i],j+dp[j]+dp[i-j]);
		}
	}
	vector<int> x,y;
	int a=n,b=n;
	for(int i=1;i<=2*n;i++){
		if(a==0){
			y.push_back(i);
			continue;
		}
		int z=Query(i);
		if(ans!=z){
			a--;
			x.push_back(i);
		}
		else{
			b--;
			y.push_back(i);
		}
		ans=z;
	}
	shuffle(x.begin(),x.end(),rnd);
	shuffle(y.begin(),y.end(),rnd);
	f(x,y,1);
}

Compilation message

minerals.cpp: In function 'void f(std::vector<int>&, std::vector<int>&, int)':
minerals.cpp:61:6: warning: unused variable 'w' [-Wunused-variable]
   61 |  int w=__lg(n-1);
      |      ^

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5876 KB Output is correct
2 Incorrect 39 ms 6344 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 29 ms 5876 KB Output is correct
6 Incorrect 39 ms 6344 KB Wrong Answer [2]
7 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 29 ms 5876 KB Output is correct
6 Incorrect 39 ms 6344 KB Wrong Answer [2]
7 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 29 ms 5876 KB Output is correct
6 Incorrect 39 ms 6344 KB Wrong Answer [2]
7 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 29 ms 5876 KB Output is correct
6 Incorrect 39 ms 6344 KB Wrong Answer [2]
7 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 29 ms 5876 KB Output is correct
6 Incorrect 39 ms 6344 KB Wrong Answer [2]
7 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 29 ms 5876 KB Output is correct
6 Incorrect 39 ms 6344 KB Wrong Answer [2]
7 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 29 ms 5876 KB Output is correct
6 Incorrect 39 ms 6344 KB Wrong Answer [2]
7 Halted 0 ms 0 KB -