Submission #784617

#	Time	Username	Problem	Language	Result	Execution time	Memory
784617		kshitij_sodani	Park (JOI17_park)	C++14	67 / 100	225 ms	680 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;
bool cmp(int aa,int bb){
	if(aa==bb){
		return false;
	}
	for(int i=0;i<n;i++){
		cur[i]=1;
	}
	cur[aa]=0;
	if(query(0,bb,cur)==1){
		return false;
	}
	else{
		return true;
	}
}
void Detect(int t, int nn) {
	int i;
	n=nn;

	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);
				}
			}
			low=-1;
			
			for(int j=0;j<n;j++){
				cur[j]=1;
			}
			vector<int> kk;
			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;
						}
						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
			}
			//you need to sort elements of kk between x and i
			for(auto j:kk){
				vis[j]=1;
			}
			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));
		}
	}

}

Compilation message (stderr)

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

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