oj.uz

답안 #908585

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
908585 2024-01-16T14:45:56 Z amirhoseinfar1385 카멜레온의 사랑 (JOI20_chameleon) C++17
0 / 100
 42 ms 612 KB 
#include "chameleon.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
int n,val[maxn];
vector<int>adj[maxn];
map<pair<int,int>,int>mp;
vector<int>allm[4];
void createmos(){
	for(int i=1;i<=n;i++){
		allm[0].push_back(i);
		val[i]=0;
	}
	for(int i=n+1;i<=2*n;i++){
		allm[1].push_back(i);
		val[i]=1;
	}
}

bool check(vector<int>now,int u){
	now.push_back(u);
	int res=Query(now);
	if(res==(int)now.size()){
		return 0;
	}
	return 1;
}

int findz(vector<int>now,int u){
//	cout<<(int)now.size()<<" "<<u<<endl;
	if((int)now.size()==1){
		return now[0];
	}
	int m=(int)now.size();
	m>>=1;
	vector<int>left,right;
	for(int i=0;i<m;i++){
		left.push_back(now[i]);
	}
	for(int i=m;i<(int)now.size();i++){
		right.push_back(now[i]);
	}
	if(check(left,u)){
		return findz(left,u);
	}
	return findz(right,u);
}

void finde(){
	for(int i=1;i<=2*n;i++){
		for(int j=0;j<4;j++){
			//cout<<i<<" "<<j<<" wtf "<<" "<<val[i]<<endl;
			if(j==val[i]){
				continue;
			}
			vector<int>tof=allm[j];
			sort(tof.begin(),tof.end());
			for(auto x:adj[i]){
				int p=lower_bound(tof.begin(),tof.end(),x)-tof.begin();
				if(p!=(int)tof.size()&&tof[p]==x){
					tof.erase(tof.begin()+p);
				}
			}
			while(check(tof,i)){
			//	cout<<"salam "<<i<<" "<<j<<endl;
				int res=findz(tof,i);
				int p=lower_bound(tof.begin(),tof.end(),res)-tof.begin();
				tof.erase(tof.begin()+p);
				adj[i].push_back(res);
				adj[res].push_back(i);
				mp[make_pair(min(i,res),max(i,res))]=1;
			}
		}
	}
}

void Solve(int N) {
  n=N;
  createmos();
 // cout<<"salam"<<endl;
  finde();
 // cout<<"by"<<endl;
  for(int i=1;i<=2*n;i++){
  	if(adj[i].size()==3){
  		int res=Query({i,adj[i][0],adj[i][1]});
  		if(res==1){
  			mp[make_pair(min(i,adj[i][2]),max(i,adj[i][2]))]=0;
  		}
  		res=Query({i,adj[i][0],adj[i][2]});
  		if(res==1){
  			mp[make_pair(min(i,adj[i][1]),max(i,adj[i][1]))]=0;
  		}
  		res=Query({i,adj[i][2],adj[i][1]});
  		if(res==1){
  			mp[make_pair(min(i,adj[i][0]),max(i,adj[i][0]))]=0;
  		}
  	}
  }
  for(auto x:mp){
  	if(x.second==1){
  	//	cout<<x.first.first<<" "<<x.first.second<<endl;
  		Answer(x.first.first,x.first.second);
  	}
  }
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 36.0

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