Submission #1008895

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1008895	2024-06-27T04:28:14 Z	emptypringlescan	Chameleon's Love (JOI20_chameleon)	C++17	44 / 100	7 ms	596 KB

chameleon

#include <bits/stdc++.h>
using namespace std;
#include "chameleon.h"
void Solve(int n){
	if(n<=50){
		vector<pair<int,int> > eds,adj[2*n+1];
		vector<int> st;
		for(int i=1; i<2*n; i++){
			for(int j=i+1; j<=2*n; j++){
				int x=Query({i,j});
				if(x==1){
					eds.push_back({i,j});
					adj[i].push_back({j,eds.size()-1});
					adj[j].push_back({i,eds.size()-1});
					st.push_back(0);
				}
			}
		}
		for(int i=1; i<=2*n; i++){
			if((int)adj[i].size()==1) continue;
			assert((int)adj[i].size()==3);
			int a=Query({i,adj[i][0].first,adj[i][1].first});
			int b=Query({i,adj[i][0].first,adj[i][2].first});
			int c=Query({i,adj[i][1].first,adj[i][2].first});
			if(a==1) st[adj[i][2].second]=1;
			if(b==1) st[adj[i][1].second]=1;
			if(c==1) st[adj[i][0].second]=1;
		}
		for(int i=0; i<(int)eds.size(); i++){
			if(st[i]==0) Answer(eds[i].first,eds[i].second);
		}
	}
	else{
		vector<int> v;
		int got[2*n+1];
		memset(got,0,sizeof(got));
		for(int i=1; i<=2*n; i++){
			v.clear();
			for(int j=1; j<=i; j++) if(!got[j]) v.push_back(j);
			int x=Query(v);
			if(x<(int)v.size()){
				int lo=1,hi=i-1,mid;
				while(lo<hi){
					mid=(lo+hi)/2;
					v.clear();
					v.push_back(i);
					for(int j=lo; j<=mid; j++) if(!got[j]) v.push_back(j);
					x=Query(v);
					if(x<(int)v.size()) hi=mid;
					else lo=mid+1;
				}
				Answer(lo,i);
				got[lo]=1;
				got[i]=1;
			}
		}
	}
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	7 ms	340 KB	Output is correct
4	Correct	7 ms	344 KB	Output is correct
5	Correct	7 ms	344 KB	Output is correct
6	Correct	7 ms	452 KB	Output is correct
7	Correct	7 ms	344 KB	Output is correct
8	Correct	7 ms	596 KB	Output is correct
9	Correct	7 ms	344 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	2 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Incorrect	1 ms	344 KB	Wrong Answer [6]
4	Halted	0 ms	0 KB	-

Subtask #5

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	7 ms	340 KB	Output is correct
4	Correct	7 ms	344 KB	Output is correct
5	Correct	7 ms	344 KB	Output is correct
6	Correct	7 ms	452 KB	Output is correct
7	Correct	7 ms	344 KB	Output is correct
8	Correct	7 ms	596 KB	Output is correct
9	Correct	7 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	0 ms	344 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	2 ms	344 KB	Output is correct
22	Correct	1 ms	344 KB	Output is correct
23	Correct	1 ms	344 KB	Output is correct
24	Correct	1 ms	344 KB	Output is correct
25	Correct	1 ms	344 KB	Output is correct
26	Correct	1 ms	344 KB	Output is correct
27	Correct	1 ms	344 KB	Output is correct
28	Correct	0 ms	344 KB	Output is correct
29	Correct	0 ms	344 KB	Output is correct
30	Incorrect	1 ms	344 KB	Wrong Answer [6]
31	Halted	0 ms	0 KB	-