제출 #784719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
784719		kshitij_sodani	Park (JOI17_park)	C++14	77 / 100	253 ms	624 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'

int query(int x,int y,int Place[]){
	return Ask(min(x,y),max(x,y),Place);
}
static int cur[1501];
vector<int> adj[1501];
int vis[1501];
int par3[1501];
vector<int> ss;
void dfs(int no,int par=-1){
	ss.pb(no);
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no);
		}
	}
}

int n;
vector<int> kk;
int xa;
bool cmp(int aa,int bb){
	if(aa==bb){
		return false;
	}
	for(int i=0;i<n;i++){
		cur[i]=0;
	}
	for(auto j:kk){
		cur[j]=1;
	}
	cur[xa]=1;
	cur[aa]=0;
	if(query(min(xa,bb),max(xa,bb),cur)==1){
		return false;
	}
	else{
		return true;
	}
}
int val[1501];
vector<int> ee;
void dfs3(int no,int par=-1){
	ee.pb(no);
	for(auto j:adj[no]){
		if(j!=par and val[j]==1){
			dfs3(j,no);
		}
	}
}
vector<pair<int,int>> ans;
void solve(int i,vector<int> tt){
	if(tt.size()==0){
		return;
	}
	for(int j=0;j<n;j++){
		val[j]=0;
	}
	for(auto j:tt){
		val[j]=1;
	}
	assert(val[i]==0);
	ee.clear();
	dfs3(tt[0]);
	for(int j=0;j<n;j++){
		cur[j]=0;
	}
	for(auto j:ee){
		cur[j]=1;
	}
	cur[i]=1;
	if(query(i,ee[0],cur)==1){
		int low=-1;
		for(int j=19;j>=0;j--){
			if(low+(1<<j)<ee.size()){
				for(int ii=0;ii<ee.size();ii++){
					if(ii<=(low+(1<<j))){
						cur[ee[ii]]=1;
					}
					else{
						cur[ee[ii]]=0;
					}
				}

				if(query(i,ee[0],cur)==0){
					low+=(1<<j);
				}
			}
		}
		low++;
		int x=ee[low];
		ans.pb({x,i});
		vector<int> mm;
		
		for(auto j:adj[x]){
			if(val[j]==1){
				mm.pb(j);
			}
		}
		val[x]=0;
		vector<vector<int>> za;
		for(auto j:mm){
			ee.clear();
			dfs3(j);
			za.pb(ee);
		}
		for(auto j:za){
			solve(i,j);
		}
	}
	else{
		return;
	}



}

void Detect(int t, int nn) {
	int i;
	n=nn;
	if(t==1){
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				for(int x=0;x<n;x++){
					cur[x]=0;
				}
				cur[i]=1;
				cur[j]=1;
				if(query(i,j,cur)==1){
					Answer(i,j);
				}
			}
		}
		return;
	}
	vis[0]=1;
	for(int i=1;i<n;i++){
		if(vis[i]==0){
			ss.clear();
			dfs(0);
			for(int j=0;j<n;j++){
				cur[j]=1;
			}
			int low=-1;
			for(int j=19;j>=0;j--){
				if(low+(1<<j)<ss.size()){
					for(int ii=0;ii<ss.size();ii++){
						if(ii<=(low+(1<<j))){
							cur[ss[ii]]=1;
						}
						else{
							cur[ss[ii]]=0;
						}
					}
				/*	if(i==2 and low+(1<<j)==0){
						for(int jj=0;jj<n;jj++){
							cout<<cur[jj]<<",,";
						}
						cout<<endl;
						cout<<query(0,i,cur)<<endl;

					}*/
					if(query(0,i,cur)==0){
						low+=(1<<j);
					}
				}
			}
			low++;
			int x=ss[low];
		/*	for(auto  j:ss){
				cout<<j<<"::";
			}
			cout<<low<<"?"<<endl;
			cout<<endl;
*/
			vector<int> tt;
			vis[i]=1;
			for(int j=0;j<n;j++){
				if(vis[j]==0){
					tt.pb(j);
				}
			}
			for(int j=0;j<n;j++){
				cur[j]=0;
			}
			for(int j=0;j<=low;j++){
				cur[ss[j]]=1;
			}
			cur[i]=1;
			low=-1;
		//	cout<<22<<endl;


			
			kk.clear();
			

			while(true){
				for(int j=19;j>=0;j--){
					if(low+(1<<j)<tt.size()){
						for(int ii=0;ii<tt.size();ii++){
							if(ii<=(low+(1<<j))){
								cur[tt[ii]]=0;
							}
							else{
								cur[tt[ii]]=1;
							}
						}
						for(auto ii:kk){
							cur[ii]=1;
						}
					/*	cout<<33<<endl;
						for(int jj=0;jj<n;jj++){
							cout<<cur[jj]<<":";
						}
						cout<<endl;*/
						if(query(0,i,cur)==1){
							low+=(1<<j);
						}
					}
				}
				//from prev to low nothing is there
				//low+1 is there
				if(low+1==tt.size()){
					break;
				}
				low++;
				kk.pb(tt[low]);
				//low+1 must be there
			}
		//	cout<<44<<endl;
			//you need to sort elements of kk between x and i
			for(auto j:kk){
				vis[j]=1;
			}
			xa=x;
			sort(kk.begin(),kk.end(),cmp);
			
			kk.pb(i);
		/*	cout<<x<<",";
			for(auto  j:kk){
				cout<<j<<",";
			}
			cout<<endl;*/
			for(auto j:kk){
				adj[x].pb(j);
				par3[j]=x;
				adj[j].pb(x);
				x=j;
			}
		}
	}
	for(int i=1;i<n;i++){
		for(auto j:adj[par3[i]]){
			if(j==i){
				continue;
			}
			ss.clear();
			dfs(j,par3[i]);
			solve(i,ss);
		}
	}
	for(int i=0;i<n;i++){
		for(auto j:adj[i]){
			if(i>j){
				continue;
			}
			//cout<<i<<":"<<j<<endl;
			Answer(min(i,j),max(i,j));
		}
	}
	for(auto j:ans){
	//	cout<<j.a<<"::"<<j.b<<endl;
		Answer(min(j.a,j.b),max(j.a,j.b));
	}

}

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'void solve(int, std::vector<int>)':
park.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    if(low+(1<<j)<ee.size()){
      |       ~~~~~~~~~~^~~~~~~~~~
park.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int ii=0;ii<ee.size();ii++){
      |                  ~~^~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:155:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     if(low+(1<<j)<ss.size()){
      |        ~~~~~~~~~~^~~~~~~~~~
park.cpp:156:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |      for(int ii=0;ii<ss.size();ii++){
      |                   ~~^~~~~~~~~~
park.cpp:209:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |      if(low+(1<<j)<tt.size()){
      |         ~~~~~~~~~~^~~~~~~~~~
park.cpp:210:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |       for(int ii=0;ii<tt.size();ii++){
      |                    ~~^~~~~~~~~~
park.cpp:233:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |     if(low+1==tt.size()){
      |        ~~~~~^~~~~~~~~~~
park.cpp:128:6: warning: unused variable 'i' [-Wunused-variable]
  128 |  int i;
      |      ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 0 / 23