제출 #784677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
784677		kshitij_sodani	Park (JOI17_park)	C++14	77 / 100	152 ms	528 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'

#define query Ask

static int cur[1501];
vector<int> adj[1501];
int vis[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;
	}
}
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);
				x=j;
			}
		}
	}
	for(int i=0;i<n;i++){
		for(auto j:adj[i]){
			//cout<<i<<":"<<j<<endl;
			Answer(min(i,j),max(i,j));
		}
	}

}

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

park.cpp: In function 'void Detect(int, int)':
park.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     if(low+(1<<j)<ss.size()){
      |        ~~~~~~~~~~^~~~~~~~~~
park.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |      for(int ii=0;ii<ss.size();ii++){
      |                   ~~^~~~~~~~~~
park.cpp:130:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |      if(low+(1<<j)<tt.size()){
      |         ~~~~~~~~~~^~~~~~~~~~
park.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |       for(int ii=0;ii<tt.size();ii++){
      |                    ~~^~~~~~~~~~
park.cpp:154:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     if(low+1==tt.size()){
      |        ~~~~~^~~~~~~~~~~
park.cpp:49:6: warning: unused variable 'i' [-Wunused-variable]
   49 |  int i;
      |      ^

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