Submission #854412

#	Time	Username	Problem	Language	Result	Execution time	Memory
854412		Wansur	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	13 ms	1208 KiB

longesttrip

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

bool are_connected(std::vector<int> A, std::vector<int> B);

bool ask(vector<int> a,vector<int> b){
	return are_connected(a,b);
}

bool ask(int a,int b){
	return are_connected({a},{b});
}

std::vector<int> longest_trip(int n, int D){
	vector<int> p1,p2;
	p1.push_back(0);
	int t=1;
	if(n%2==0){
		t++;
		if(ask({0},{1})){
			p1.push_back(1);
		}
		else{
			p2.push_back(1);
		}
	}
	for(int i=t;i<n;i+=2){
		if(!p2.size()){
			if(ask(i,i+1)){
				if(ask(i,p1.back())){
					p1.push_back(i);
					p1.push_back(i+1);
				}
				else if(ask(i+1,p1.back())){
					p1.push_back(i+1);
					p1.push_back(i);
				}
				else{
					p2.push_back(i);
					p2.push_back(i+1);
				}
			}
			else{
				if(ask(i,p1.back())){
					p1.push_back(i);
					p2.push_back(i+1);
				}
				else{
					p1.push_back(i+1);
					p2.push_back(i);
				}
			}
		}
		else{
			if(ask(i,i+1)){
				if(ask(i,p1.back())){
					p1.push_back(i);
					p1.push_back(i+1);
					if(ask(i+1,p2.back())){
						reverse(p2.begin(),p2.end());
						for(int x:p2){
							p1.push_back(x);
						}
						p2.clear();
					}
				}
				else{
					p2.push_back(i);
					p2.push_back(i+1);
					if(ask(i+1,p1.back())){
						reverse(p2.begin(),p2.end());
						for(int x:p2){
							p1.push_back(x);
						}
						p2.clear();
					}
				}
			}
			else{
				int x=ask(i,p1.back());
				if(x){
					if(ask(i+1,p2.back())){
						p1.push_back(i);
						p2.push_back(i+1);
					}
					else{
						p2.push_back(i);
						p1.push_back(i+1);
					}
				}
				else{
					p2.push_back(i);
					p1.push_back(i+1);
				}
			}
		}
	}
	if(p2.size()==0){
		return p1;
	}
	if(!ask(p1,p2)){
		if(p1.size()>p2.size()){
			return p1;
		}
		return p2;
	}
	if((p1.size()==1 || ask(p1[0],p1.back())) && (p2.size()==1 || ask(p2[0],p2.back()))){
		int pos1=0,pos2=0;
		for(int l=0,r=p1.size()-1;l<=r;){
			int mid=l+r>>1;
			vector<int> t;
			for(int i=0;i<=mid;i++){
				t.push_back(p1[i]);
			}
			if(ask(t,p2)){
				pos1=mid;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		for(int l=0,r=p2.size()-1;l<=r;){
			int mid=l+r>>1;
			vector<int> t;
			for(int i=0;i<=mid;i++){
				t.push_back(p2[i]);
			}
			if(ask(t,{p1[pos1]})){
				pos2=mid;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		vector<int> a,b;
		for(int i=pos1;i<p1.size();i++){
			a.push_back(p1[i]);
		}
		for(int i=0;i<pos1;i++){
			a.push_back(p1[i]);
		}
		for(int i=pos2;i<p2.size();i++){
			b.push_back(p2[i]);
		}
		for(int i=0;i<pos2;i++){
			b.push_back(p2[i]);
		}
		reverse(a.begin(),a.end());
		for(int x:b){
			a.push_back(x);
		}
		return a;
	}
	if(ask(p1.back(),p2[0])){
		for(int x:p2){
			p1.push_back(x);
		}
		return p1;
	}
	if(ask(p1.back(),p2.back())){
		reverse(p2.begin(),p2.end());
		for(int x:p2){
			p1.push_back(x);
		}
		return p1;
	}
	if(ask(p1[0],p2[0])){
		reverse(p1.begin(),p1.end());
		for(int x:p2){
			p1.push_back(x);
		}
		return p1;
	}
	for(int x:p1){
		p2.push_back(x);
	}
	return p2;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:111:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |    int mid=l+r>>1;
      |            ~^~
longesttrip.cpp:125:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |    int mid=l+r>>1;
      |            ~^~
longesttrip.cpp:139:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   for(int i=pos1;i<p1.size();i++){
      |                  ~^~~~~~~~~~
longesttrip.cpp:145:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |   for(int i=pos2;i<p2.size();i++){
      |                  ~^~~~~~~~~~

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