oj.uz

Submission #823069

# Submission time Handle Problem Language Result Execution time Memory
823069 2023-08-12T07:34:37 Z ymm Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 126476 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++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 n, k;

void init(int k, std::vector<int> r) {
	::k = k;
	n = r.size();
	Loop (_,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+1,p+k) {
			int i = ii%n;
			if (r[i] != -1) {
				A[i].push_back(p);
			}
		}
		Loop (ii,p-k+1,p) {
			int i = (ii+n)%n;
			if (r[i] != -1) {
				A[i].push_back(p);
				r[i]--;
			}
		}
		r[p] = -1;
	}
}

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) {
	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:23:3: note: in expansion of macro 'Loop'
   23 |   Loop (i,0,z.size()) {
      |   ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 61 ms 8760 KB Output is correct
7 Correct 655 ms 10712 KB Output is correct
8 Execution timed out 4027 ms 13160 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 659 ms 10752 KB Output is correct
7 Execution timed out 4043 ms 126476 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 659 ms 10752 KB Output is correct
7 Execution timed out 4043 ms 126476 KB Time limit exceeded
8 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 5004 KB Output is correct
3 Correct 1432 ms 9612 KB Output is correct
4 Execution timed out 4049 ms 13188 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 5004 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5004 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 39 ms 5876 KB Output is correct
8 Correct 309 ms 6064 KB Output is correct
9 Correct 60 ms 5964 KB Output is correct
10 Correct 297 ms 6076 KB Output is correct
11 Correct 40 ms 5964 KB Output is correct
12 Correct 74 ms 5892 KB Output is correct
13 Correct 684 ms 6592 KB Output is correct

Subtask #6
0 / 15.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 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 44 ms 5744 KB Output is correct
6 Execution timed out 4067 ms 31304 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 61 ms 8760 KB Output is correct
7 Correct 655 ms 10712 KB Output is correct
8 Execution timed out 4027 ms 13160 KB Time limit exceeded
9 Halted 0 ms 0 KB -