답안 #532905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532905	2022-03-04T08:13:37 Z	Koosha_mv	Minerals (JOI19_minerals)	C++14	40 / 100	1000 ms	3204 KB

minerals

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #532905

Compilation message