oj.uz

답안 #1008995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008995 2024-06-27T07:39:54 Z emptypringlescan 카멜레온의 사랑 (JOI20_chameleon) C++17
0 / 100
 4 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
#include "chameleon.h"
vector<pair<int,int> > eds,adj[1005];
vector<int> st,v;
unordered_set<int> disj[2];
int vis[1005];
void change(int x, int g){
	if(disj[g].find(x)==disj[g].end()) return;
	disj[g].erase(x);
	disj[g^1].insert(x);
	v[x]=1;
	for(auto i:adj[x]){
		if(!v[i.first]) change(i.first,g^1);
	}
}
void Solve(int n){
	int x;
	for(int i=1; i<=2*n; i++){
		vector<int> ds;
		for(int j:disj[0]) ds.push_back(j);
		int lo=0,hi=(int)ds.size(),mid;
		while(lo<hi){
			mid=(lo+hi)/2;
			v.clear();
			v.push_back(i);
			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
			x=Query(v);
			if(x<(int)v.size()) hi=mid;
			else lo=mid+1;
		}
		if((int)ds.size()>lo){
			eds.push_back({ds[lo],i});
			adj[i].push_back({ds[lo],eds.size()-1});
			adj[ds[lo]].push_back({i,eds.size()-1});
			st.push_back(0);
		}
		
		lo++,hi=(int)ds.size();
		while(lo<hi){
			mid=(lo+hi)/2;
			v.clear();
			v.push_back(i);
			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
			x=Query(v);
			if(x<(int)v.size()) hi=mid;
			else lo=mid+1;
		}
		if((int)ds.size()>lo){
			eds.push_back({ds[lo],i});
			adj[i].push_back({ds[lo],eds.size()-1});
			adj[ds[lo]].push_back({i,eds.size()-1});
			st.push_back(0);
		}
		
		lo++,hi=(int)ds.size();
		while(lo<hi){
			mid=(lo+hi)/2;
			v.clear();
			v.push_back(i);
			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
			x=Query(v);
			if(x<(int)v.size()) hi=mid;
			else lo=mid+1;
		}
		if((int)ds.size()>lo){
			eds.push_back({ds[lo],i});
			adj[i].push_back({ds[lo],eds.size()-1});
			adj[ds[lo]].push_back({i,eds.size()-1});
			st.push_back(0);
		}
		
		ds.clear();
		for(int j:disj[1]) ds.push_back(j);
		lo=0,hi=(int)ds.size();
		while(lo<hi){
			mid=(lo+hi)/2;
			v.clear();
			v.push_back(i);
			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
			x=Query(v);
			if(x<(int)v.size()) hi=mid;
			else lo=mid+1;
		}
		if((int)ds.size()>lo){
			for(int j=0; j<=500; j++) vis[j]=0;
			change(ds[lo],1);
			eds.push_back({ds[lo],i});
			adj[i].push_back({ds[lo],eds.size()-1});
			adj[ds[lo]].push_back({i,eds.size()-1});
			st.push_back(0);
		}
		
		lo++,hi=(int)ds.size();
		while(lo<hi){
			mid=(lo+hi)/2;
			v.clear();
			v.push_back(i);
			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
			x=Query(v);
			if(x<(int)v.size()) hi=mid;
			else lo=mid+1;
		}
		if((int)ds.size()>lo){
			for(int j=0; j<=500; j++) vis[j]=0;
			change(ds[lo],1);
			eds.push_back({ds[lo],i});
			adj[i].push_back({ds[lo],eds.size()-1});
			adj[ds[lo]].push_back({i,eds.size()-1});
			st.push_back(0);
		}
		
		lo++,hi=(int)ds.size();
		while(lo<hi){
			mid=(lo+hi)/2;
			v.clear();
			v.push_back(i);
			for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
			x=Query(v);
			if(x<(int)v.size()) hi=mid;
			else lo=mid+1;
		}
		if((int)ds.size()>lo){
			for(int j=0; j<=500; j++) vis[j]=0;
			change(ds[lo],1);
			eds.push_back({ds[lo],i});
			adj[i].push_back({ds[lo],eds.size()-1});
			adj[ds[lo]].push_back({i,eds.size()-1});
			st.push_back(0);
		}
		
		disj[1].insert(i);
	}
	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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 1 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 0 ms 600 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 0 ms 600 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 4 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

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 Runtime error 1 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -