oj.uz

Submission #1108700

# Submission time Handle Problem Language Result Execution time Memory
1108700 2024-11-04T19:35:48 Z jerzyk Longest Trip (IOI23_longesttrip) C++17
15 / 100
 19 ms 592 KB 
#include <bits/stdc++.h>
#include "longesttrip.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const int N = 1000 * 1000 + 7;

bool SQ(int a, int b)
{
	vector<int> v1 = {a}, v2 = {b};
	return are_connected(v1, v2);
}

void J(vector<int> &a, vector<int> &b)
{
	for(int i = 0; i < (int)b.size(); ++i)
		a.pb(b[i]);
	b.clear();
}

void R(vector<int> &a, int r)
{
	vector<int> nw;
	for(int i = r; i < (int)a.size(); ++i)
		nw.pb(a[i]);
	for(int i = 0; i < r; ++i)
		nw.pb(a[i]);
	a = nw;
}

void Merge(vector<int> &a, vector<int> &b)
{
	for(int r = 0; r < 2; ++r)
	{
		for(int l = 0; l < 2; ++l)
		{
			if(SQ(a.back(), b[0]))
			{
				J(a, b);
				return;
			}
			reverse(b.begin(), b.end());
		}
		reverse(a.begin(), a.end());
	}
	int p, s, k;
	vector<int> q1, qd;
	p = 0, k = (int)a.size();
	while(p < k)
	{
		s = (p + k) / 2;
		q1.clear();
		for(int i = 0; i <= s; ++i)
			q1.pb(a[i]);
		if(are_connected(q1, b))
			k = s;
		else
			p = s + 1;
	}
	if(p == (int)a.size()) return;

	R(a, p);
	qd = {a[0]};
	p = 0, k = (int)b.size();
	while(p < k)
	{
		s = (p + k) / 2;
		q1.clear();
		for(int i = 0; i <= s; ++i)
			q1.pb(b[i]);
		if(are_connected(q1, qd))
			k = s;
		else
			p = s + 1;
	}
	R(b, p);
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	J(a, b);
}

vector<int> longest_trip(int _N, int _X_D)
{
	int n = _N;
	vector<int> l1, l2;
	l1.pb(0);

	if(n == 1) return l1;

	for(int i = 1; i < n; ++i)
	{
		if(SQ(i, l1.back()))
		{
			l1.pb(i);
			continue;
		}
		if((int)l2.size() == 0 || SQ(i, l2.back()))
		{
			l2.pb(i);
			continue;
		}
		reverse(l2.begin(), l2.end());
		J(l1, l2);

		l2.pb(i);
	}
	if(l1.size() < l2.size())
		swap(l1, l2);
	if(l2.size() == 0)
		return l1;
	Merge(l1, l2);
	return l1;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 4 ms 492 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 336 KB Output is correct
2 Correct 7 ms 336 KB Output is correct
3 Correct 7 ms 336 KB Output is correct
4 Correct 8 ms 336 KB Output is correct
5 Correct 7 ms 336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 336 KB Output is correct
2 Correct 7 ms 508 KB Output is correct
3 Correct 9 ms 336 KB Output is correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 9 ms 436 KB Output is correct
6 Correct 10 ms 336 KB Output is correct
7 Correct 9 ms 336 KB Output is correct
8 Correct 8 ms 336 KB Output is correct
9 Correct 7 ms 336 KB Output is correct
10 Correct 8 ms 336 KB Output is correct
11 Correct 9 ms 336 KB Output is correct
12 Correct 8 ms 592 KB Output is correct
13 Correct 7 ms 336 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 336 KB Output is correct
2 Correct 10 ms 336 KB Output is correct
3 Correct 9 ms 336 KB Output is correct
4 Correct 8 ms 336 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 11 ms 336 KB Output is correct
7 Correct 10 ms 336 KB Output is correct
8 Correct 8 ms 336 KB Output is correct
9 Correct 7 ms 336 KB Output is correct
10 Correct 8 ms 336 KB Output is correct
11 Correct 8 ms 444 KB Output is correct
12 Correct 9 ms 336 KB Output is correct
13 Correct 7 ms 336 KB Output is correct
14 Correct 19 ms 336 KB Output is correct
15 Correct 16 ms 336 KB Output is correct
16 Incorrect 2 ms 336 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 336 KB Output is correct
2 Correct 8 ms 336 KB Output is correct
3 Correct 8 ms 336 KB Output is correct
4 Correct 10 ms 336 KB Output is correct
5 Correct 9 ms 592 KB Output is correct
6 Correct 11 ms 352 KB Output is correct
7 Correct 11 ms 336 KB Output is correct
8 Correct 7 ms 336 KB Output is correct
9 Correct 10 ms 336 KB Output is correct
10 Correct 8 ms 592 KB Output is correct
11 Correct 8 ms 336 KB Output is correct
12 Correct 8 ms 336 KB Output is correct
13 Correct 8 ms 336 KB Output is correct
14 Correct 18 ms 336 KB Output is correct
15 Correct 13 ms 336 KB Output is correct
16 Incorrect 2 ms 336 KB Incorrect
17 Halted 0 ms 0 KB -