oj.uz

답안 #854410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854410 2023-09-27T11:37:23 Z Wansur 가장 긴 여행 (IOI23_longesttrip) C++17
5 / 100
 6 ms 600 KB 
#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()) || ask(i+1,p1.back())){
					p1.push_back(i);
					p1.push_back(i+1);
				}
				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()) || ask(i+1,p1.back())){
					p1.push_back(i);
					p1.push_back(i+1);
				}
				else{
					p2.push_back(i);
					p2.push_back(i+1);
				}
			}
			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(ask(p1[0],p1.back()) && 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

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

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 516 KB Output is correct
2 Incorrect 2 ms 436 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 596 KB Output is correct

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Incorrect 0 ms 344 KB non-disjoint arrays
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Incorrect 1 ms 344 KB non-disjoint arrays
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Incorrect 0 ms 596 KB non-disjoint arrays
7 Halted 0 ms 0 KB -