oj.uz

답안 #1008928

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008928 2024-06-27T05:41:17 Z emptypringlescan 카멜레온의 사랑 (JOI20_chameleon) C++17
24 / 100
 16 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
#include "chameleon.h"
void Solve(int n){
	if(n<=0){
		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));
		bool st1=false;
		for(int i=1; i<=2*n; i++){
			if(i>n&&!st1) break;
			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()){
				if(i<=n) st1=true;
				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;
			}
		}
		if(!st1){
			vector<pair<int,int> > eds,adj[2*n+1];
			vector<int> st;
			int x;
			for(int i=n+1; i<=2*n; i++){
				int lo=1,hi=n,mid;
				while(lo<hi){
					mid=(lo+hi)/2;
					v.clear();
					v.push_back(i);
					for(int j=lo; j<=mid; j++) v.push_back(j);
					x=Query(v);
					if(x<(int)v.size()) hi=mid;
					else lo=mid+1;
				}
				eds.push_back({lo,i});
				adj[i].push_back({lo,eds.size()-1});
				adj[lo].push_back({i,eds.size()-1});
				st.push_back(0);
				
				lo++,hi=n+1;
				while(lo<hi){
					mid=(lo+hi)/2;
					v.clear();
					v.push_back(i);
					for(int j=lo; j<=mid; j++) v.push_back(j);
					x=Query(v);
					if(x<(int)v.size()) hi=mid;
					else lo=mid+1;
				}
				if(lo==n+1) continue;
				eds.push_back({lo,i});
				adj[i].push_back({lo,eds.size()-1});
				adj[lo].push_back({i,eds.size()-1});
				st.push_back(0);
				
				lo++,hi=n+1;
				while(lo<hi){
					mid=(lo+hi)/2;
					v.clear();
					v.push_back(i);
					for(int j=lo; j<=mid; j++) v.push_back(j);
					x=Query(v);
					if(x<(int)v.size()) hi=mid;
					else lo=mid+1;
				}
				if(lo==n+1) continue;
				eds.push_back({lo,i});
				adj[i].push_back({lo,eds.size()-1});
				adj[lo].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);
			}
		}
	}
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 7 ms 448 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 7 ms 452 KB Output is correct
8 Correct 8 ms 344 KB Output is correct
9 Correct 7 ms 344 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 15 ms 456 KB Output is correct
4 Correct 15 ms 344 KB Output is correct
5 Correct 15 ms 344 KB Output is correct
6 Correct 15 ms 344 KB Output is correct
7 Correct 16 ms 344 KB Output is correct
8 Correct 16 ms 512 KB Output is correct
9 Correct 16 ms 344 KB Output is correct

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 7 ms 448 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 7 ms 452 KB Output is correct
8 Correct 8 ms 344 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 0 ms 344 KB Wrong Answer [6]
12 Halted 0 ms 0 KB -