oj.uz

Submission #1018333

# Submission time Handle Problem Language Result Execution time Memory
1018333 2024-07-09T19:07:32 Z Boas Comparing Plants (IOI20_plants) C++17
5 / 100
 80 ms 7504 KB 
#include "plants.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define loop(x, i) for (int i = 0; i < (x); i++)
#define ALL(x) (x).begin(), x.end()
#define pb push_back

vii increasingSegs;
vii decreasingSegs;
int N;
int beg = 0;

void init(int k, vi r)
{
	if (k != 2)
		throw;
	N = r.size();
	for (int i = 0; i < N; i++)
	{
		if (r[i] != r[(i - 1 + N) % N])
		{
			beg = i;
			break;
		}
	}
	int start = 0;
	int prev = r[start + beg];
	for (int i = 1; i <= N; i++)
	{
		int p = (i + beg) % N;
		if (r[p] != prev)
		{
			if (prev == 1)
			{
				increasingSegs.pb({start, i});
			}
			else
			{
				decreasingSegs.pb({start, i});
			}
			start = i;
		}
		prev = r[p];
	}
	return;
}

int compare_plants(int x, int y)
{
	int a = (x - beg + N) % N, b = (y - beg + N) % N;
	auto it = lower_bound(ALL(increasingSegs), ii{min(a, b) + 1, -1});
	auto it2 = lower_bound(ALL(decreasingSegs), ii{min(a, b) + 1, -1});
	if (it != increasingSegs.begin())
	{
		it = prev(it);
		if (it->first <= a && a <= it->second)
		{
			if (it->first <= b && b <= it->second)
			{
				if (b > a)
					return -1;
				return 1;
			}
		}
	}
	if (it2 != decreasingSegs.begin())
	{
		it2 = prev(it2);
		if (it2->first <= a && a <= it2->second)
		{
			if (it2->first <= b && b <= it2->second)
			{
				if (b > a)
					return 1;
				return -1;
			}
		}
	}
	if (a == 0 || b == 0)
	{
		int other = max(a, b);
		if (increasingSegs.back().second == N && increasingSegs.back().first <= other)
		{
			if (a == 0)
				return 1;
			return -1;
		}
		if (decreasingSegs.back().second == N && decreasingSegs.back().first <= other)
		{
			if (a == 0)
				return -1;
			return 1;
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 37 ms 4064 KB Output is correct
7 Correct 45 ms 5416 KB Output is correct
8 Correct 80 ms 7504 KB Output is correct
9 Correct 66 ms 7252 KB Output is correct
10 Correct 60 ms 7252 KB Output is correct
11 Correct 55 ms 7252 KB Output is correct
12 Correct 57 ms 7248 KB Output is correct
13 Correct 46 ms 7248 KB Output is correct
14 Correct 54 ms 7256 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 0 ms 348 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 0 ms 348 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 0 ms 432 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Runtime error 1 ms 348 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 37 ms 4064 KB Output is correct
7 Correct 45 ms 5416 KB Output is correct
8 Correct 80 ms 7504 KB Output is correct
9 Correct 66 ms 7252 KB Output is correct
10 Correct 60 ms 7252 KB Output is correct
11 Correct 55 ms 7252 KB Output is correct
12 Correct 57 ms 7248 KB Output is correct
13 Correct 46 ms 7248 KB Output is correct
14 Correct 54 ms 7256 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Runtime error 0 ms 348 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -