Submission #1067328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067328		pcc	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	11 ms	856 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

#define vi vector<int>

const int mxn = 300;

int N;
int dp[mxn][mxn];

int ask(vi a,vi b){
	return are_connected(a,b);
}
int ask(int a,int b){
	if(a == b)return 1;
	if(dp[a][b] != -1)return dp[a][b];
	return dp[a][b] = dp[b][a] = ask(vi({a}),vi({b}));
}

vi to_vec(deque<int> a){
	vi re;
	for(auto &i:a)re.push_back(i);
	return re;
}
int ask(deque<int> a,deque<int> b){
	return ask(to_vec(a),to_vec(b));
}

std::vector<int> longest_trip(int NN, int D){
	memset(dp,-1,sizeof(dp));
	deque<int> dq[2];
	N = NN;
	set<int> st;
	for(int i =0;i<N;i++)st.insert(i);
	if(ask(0,1))dq[0] = {0,1};
	else if(ask(0,2))dq[0] = {0,2};
	else dq[0] = {1,2};
	for(auto &i:dq[0])st.erase(i);
	while(st.size()){
		if(dq[1].empty()){
			dq[1].push_back(*st.begin());
			st.erase(*st.begin());
			continue;
		}
		vector<int> now;
		for(int i = 0;i<2&&!st.empty();i++){
			now.push_back(*st.begin());
			st.erase(*st.begin());
		}
		if(now.size() == 1){
			int tmp = now[0];
			if(ask(dq[0].back(),tmp))dq[0].push_back(tmp);
			else if(ask(dq[1].back(),tmp))dq[1].push_back(tmp);
			else{
				while(!dq[1].empty()){
					dq[0].push_back(dq[1].back());
					dq[1].pop_back();
				}
				dq[1] = {tmp};
			}
		}
		else{
			int a = now[0],b = now[1];
			if(ask(a,b)){
				if(ask(dq[0].back(),a)){
					dq[0].push_back(a);
					dq[0].push_back(b);
				}
				else if(ask(dq[1].back(),a)){
					dq[1].push_back(a);
					dq[1].push_back(b);
				}
				else{
					while(!dq[1].empty()){
						dq[0].push_back(dq[1].back());
						dq[1].pop_back();
					}
					dq[1] = {a,b};
				}
			}
			else{
				if(ask(dq[0].back(),a)){
					dq[0].push_back(a);
				}
				else{
					dq[1].push_back(a);
					dq[1].swap(dq[0]);
				}
				if(ask(dq[1].back(),b)){
					dq[1].push_back(b);
				}
				else{
					while(!dq[1].empty()){
						dq[0].push_back(dq[1].back());
						dq[1].pop_back();
					}
					dq[1] = {b};
				}
			}
			if(dq[0].size()<dq[1].size())dq[0].swap(dq[1]);
		}
	}
	/*
	cerr<<"PHASE 1 done!"<<endl;
	for(auto &i:dq[0])cerr<<i<<',';cerr<<endl;
	for(auto &i:dq[1])cerr<<i<<',';cerr<<endl;cerr<<"--------------------------------"<<endl;
	*/
	assert(dq[0].size()>=dq[1].size());
	if(dq[1].empty()||!ask(dq[0],dq[1])){
		return to_vec(dq[0]);
	}
	//cerr<<"CHECK CHAIN DONE!"<<endl;
	if(ask(dq[0][0],dq[1][0])){
		while(!dq[1].empty()){
			dq[0].push_front(dq[1][0]);
			dq[1].pop_front();
		}
		return to_vec(dq[0]);
	}
	else if(ask(dq[0][0],dq[1].back())){
		while(!dq[1].empty()){
			dq[0].push_front(dq[1].back());
			dq[1].pop_back();
		}
		return to_vec(dq[0]);
	}
	else if(ask(dq[0].back(),dq[1][0])){
		while(!dq[1].empty()){
			dq[0].push_back(dq[1].front());
			dq[1].pop_front();
		}
		return to_vec(dq[0]);
	}
	else if(ask(dq[0].back(),dq[1].back())){
		while(!dq[1].empty()){
			dq[0].push_back(dq[1].back());
			dq[1].pop_back();
		}
		return to_vec(dq[0]);
	}
	else{
		deque<int> d0 = dq[0],d1 = dq[1];
		while(dq[1].size()>1){
			int mid = dq[1].size()>>1;
			deque<int> c;
			for(int i = 0;i<mid;i++)c.push_back(dq[1][i]);
			if(ask(dq[0],c))while(dq[1].size()>mid)dq[1].pop_back();
			else for(int i = 0;i<mid;i++)dq[1].pop_front();
		}
		while(dq[0].size()>1){
			int mid = dq[0].size()>>1;
			deque<int> c;
			for(int i = 0;i<mid;i++)c.push_back(dq[0][i]);
			if(ask(c,dq[1]))while(dq[0].size()>mid)dq[0].pop_back();
			else for(int i = 0;i<mid;i++)dq[0].pop_front();
		}
		int a = dq[0][0],b = dq[1][0];
		dq[0] = d0,dq[1] = d1;
		while(dq[0][0] != a){
			dq[0].push_back(dq[0][0]);
			dq[0].pop_front();
		}
		while(dq[1][0] != b){
			dq[1].push_back(dq[1][0]);
			dq[1].pop_front();
		}
		while(!dq[1].empty()){
			dq[0].push_front(dq[1].front());
			dq[1].pop_front();
		}
		return to_vec(dq[0]);
	}
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:148:38: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  148 |    if(ask(dq[0],c))while(dq[1].size()>mid)dq[1].pop_back();
      |                          ~~~~~~~~~~~~^~~~
longesttrip.cpp:155:38: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  155 |    if(ask(c,dq[1]))while(dq[0].size()>mid)dq[0].pop_back();
      |                          ~~~~~~~~~~~~^~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60