oj.uz

Submission #823084

# Submission time Handle Problem Language Result Execution time Memory
823084 2023-08-12T07:45:01 Z ymm Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 13404 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= l; --x)
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 200'010;
vector<int> A[N];
int val[N];
int n, k;

void init(int k, std::vector<int> r) {
	::k = k;
	n = r.size();
	LoopR (x,0,n) {
		vector<int> z;
		Loop (i,0,n) {
			if (r[i] == 0)
				z.push_back(i);
		}
		int p = -1;
		Loop (i,0,z.size()) {
			if (z[i] - (i == 0? z.back() - n: z[i-1]) >= k) {
				p = z[i];
				break;
			}
		}
		assert(p != -1);
		Loop (ii,p-k+1,p) {
			int i = (ii+n)%n;
			if (r[i] != -1)
				r[i]--;
		}
		r[p] = -1;
		val[p] = x;
	}
	//int mx = 0;
	//while (val[mx] != n-1)
	//	++mx;
	//vector<int> vec = {mx};
	//Loop (ii,mx+1,mx+n) {
	//	int i = ii%n;
	//	while (val[vec.back()] < val[i])
	//		vec.pop_back();
	//	A[i].push_back(vec.back());
	//	vec.push_back(i);
	//}
	//vec = {mx};
	//LoopR (ii,mx-n+1,mx) {
	//	int i = (ii+n)%n;
	//	while (val[vec.back()] < val[i])
	//		vec.pop_back();
	//	A[i].push_back(vec.back());
	//	vec.push_back(i);
	//}
}

bool vis[N];
bool dfs(int v, int dst)
{
	if (v == dst)
		return 1;
	vis[v] = 1;
	for (int u : A[v]) {
		if (!vis[u] && dfs(u, dst))
			return 1;
	}
	return 0;
}

int compare_plants(int x, int y) {
	if (val[x] > val[y])
		return 1;
	else
		return -1;
	//memset(vis, 0, n);
	//if (dfs(x, y))
	//	return -1;
	//memset(vis, 0, n);
	//if (dfs(y, x))
	//	return 1;
	//return 0;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
plants.cpp:25:3: note: in expansion of macro 'Loop'
   25 |   Loop (i,0,z.size()) {
      |   ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4960 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5004 KB Output is correct
4 Incorrect 2 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4996 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 8 ms 5108 KB Output is correct
7 Correct 154 ms 9800 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 8 ms 5020 KB Output is correct
10 Correct 149 ms 9688 KB Output is correct
11 Correct 128 ms 9700 KB Output is correct
12 Correct 113 ms 9820 KB Output is correct
13 Correct 178 ms 9688 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4996 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 8 ms 5108 KB Output is correct
7 Correct 154 ms 9800 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 8 ms 5020 KB Output is correct
10 Correct 149 ms 9688 KB Output is correct
11 Correct 128 ms 9700 KB Output is correct
12 Correct 113 ms 9820 KB Output is correct
13 Correct 178 ms 9688 KB Output is correct
14 Correct 1499 ms 10192 KB Output is correct
15 Execution timed out 4005 ms 13404 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5004 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 47 ms 9500 KB Output is correct
4 Execution timed out 4054 ms 12912 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 2 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 5012 KB Output is correct
3 Incorrect 2 ms 5004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4960 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5004 KB Output is correct
4 Incorrect 2 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -