oj.uz

Submission #532905

# Submission time Handle Problem Language Result Execution time Memory
532905 2022-03-04T08:13:37 Z Koosha_mv Minerals (JOI19_minerals) C++14
40 / 100
 1000 ms 3204 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#include "minerals.h"

const int N=1e5+99;

int n,last,s[N],t[N],L[N],R[N],mark[N];
vector<pair<int,int>> Ans;
vector<int> A,B;
/*
void Answer(int a, int b){
	cout<<a<<" edge "<<b<<endl;
}
int Query(int x){
	int res=0;
	f(i,1,n+1) if(mark[s[i]] || mark[t[i]]) res++;
	cout<<"? "<<x<<" "<<res<<endl;
	return res;
}*/
bool ask(int x){
	mark[x]^=1;
	int p=Query(x),res=(p!=last);
	last=p;
	return res;
}
void reset(){
	f(i,1,2*n+1) ask(i);
}
void get(int l,int r){
	f(i,0,l) if(mark[B[i]]) ask(B[i]);
	f(i,r,n) if(mark[B[i]]) ask(B[i]);
	f(i,l,r) if(!mark[B[i]]) ask(B[i]);
}
void solve(int l,int r,vector<int> vec){
	if(l+1==r){
		Ans.pb({vec[0],B[l]});
		return ;
	}
	vector<int> a,b;
	int mid=(l+r)>>1;
	get(l,mid);
	for(auto x : vec){
		if(ask(x)==0) a.pb(x);
		else b.pb(x);
	}
	solve(l,mid,a);
	solve(mid,r,b);
}
void Solve(int N){
	n=N;
	f(i,1,2*n+1){
		if(ask(i)) A.pb(i);
		else B.pb(i);
	}
	solve(0,n,A);
	for(auto p : Ans){
		Answer(p.F,p.S);
	}
}
/*
main(){
	int n;
	cin>>n;
	f(i,1,n+1){
		cin>>s[i]>>t[i];
	}
	Solve(n);
}*/

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 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 8 ms 420 KB Output is correct
3 Correct 17 ms 580 KB Output is correct
4 Correct 52 ms 832 KB Output is correct
5 Correct 195 ms 1452 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 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 328 KB Output is correct
6 Correct 8 ms 420 KB Output is correct
7 Correct 17 ms 580 KB Output is correct
8 Correct 52 ms 832 KB Output is correct
9 Correct 195 ms 1452 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 84 ms 1064 KB Output is correct
12 Correct 177 ms 1432 KB Output is correct
13 Correct 218 ms 1568 KB Output is correct
14 Correct 173 ms 1364 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 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 328 KB Output is correct
6 Correct 8 ms 420 KB Output is correct
7 Correct 17 ms 580 KB Output is correct
8 Correct 52 ms 832 KB Output is correct
9 Correct 195 ms 1452 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 84 ms 1064 KB Output is correct
12 Correct 177 ms 1432 KB Output is correct
13 Correct 218 ms 1568 KB Output is correct
14 Correct 173 ms 1364 KB Output is correct
15 Execution timed out 1281 ms 3204 KB Time limit exceeded
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 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 328 KB Output is correct
6 Correct 8 ms 420 KB Output is correct
7 Correct 17 ms 580 KB Output is correct
8 Correct 52 ms 832 KB Output is correct
9 Correct 195 ms 1452 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 84 ms 1064 KB Output is correct
12 Correct 177 ms 1432 KB Output is correct
13 Correct 218 ms 1568 KB Output is correct
14 Correct 173 ms 1364 KB Output is correct
15 Execution timed out 1281 ms 3204 KB Time limit exceeded
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 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 328 KB Output is correct
6 Correct 8 ms 420 KB Output is correct
7 Correct 17 ms 580 KB Output is correct
8 Correct 52 ms 832 KB Output is correct
9 Correct 195 ms 1452 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 84 ms 1064 KB Output is correct
12 Correct 177 ms 1432 KB Output is correct
13 Correct 218 ms 1568 KB Output is correct
14 Correct 173 ms 1364 KB Output is correct
15 Execution timed out 1281 ms 3204 KB Time limit exceeded
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 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 328 KB Output is correct
6 Correct 8 ms 420 KB Output is correct
7 Correct 17 ms 580 KB Output is correct
8 Correct 52 ms 832 KB Output is correct
9 Correct 195 ms 1452 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 84 ms 1064 KB Output is correct
12 Correct 177 ms 1432 KB Output is correct
13 Correct 218 ms 1568 KB Output is correct
14 Correct 173 ms 1364 KB Output is correct
15 Execution timed out 1281 ms 3204 KB Time limit exceeded
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 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 328 KB Output is correct
6 Correct 8 ms 420 KB Output is correct
7 Correct 17 ms 580 KB Output is correct
8 Correct 52 ms 832 KB Output is correct
9 Correct 195 ms 1452 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 84 ms 1064 KB Output is correct
12 Correct 177 ms 1432 KB Output is correct
13 Correct 218 ms 1568 KB Output is correct
14 Correct 173 ms 1364 KB Output is correct
15 Execution timed out 1281 ms 3204 KB Time limit exceeded
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 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 328 KB Output is correct
6 Correct 8 ms 420 KB Output is correct
7 Correct 17 ms 580 KB Output is correct
8 Correct 52 ms 832 KB Output is correct
9 Correct 195 ms 1452 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 84 ms 1064 KB Output is correct
12 Correct 177 ms 1432 KB Output is correct
13 Correct 218 ms 1568 KB Output is correct
14 Correct 173 ms 1364 KB Output is correct
15 Execution timed out 1281 ms 3204 KB Time limit exceeded
16 Halted 0 ms 0 KB -