oj.uz

Submission #823092

# Submission time Handle Problem Language Result Execution time Memory
823092 2023-08-12T07:58:05 Z ymm Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 12824 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], pos[N];
int n, k;

namespace seg1 {
	int a[2*N];
	void init() { fill(a, a+2*N, N); }

	void up(int p, int x) {
		p += N;
		while (p > 0) {
			a[p] = x;
			p /= 2;
		}
	}
	int get(int l, int r) {
		l += N;
		r += N;
		int ans = N;
		while (l < r) {
			if (l&1) ans = min(ans, a[l++]);
			if (r&1) ans = min(ans, a[--r]);
			l /= 2;
			r /= 2;
		}
		return ans;
	}
	int getc(int l, int r) {
		--r;
		l = (l%n+n)%n;
		r = (r%n+n)%n;
		++r;
		if (l >= r)
			return min(get(0, r), get(l, n));
		else
			return get(l, r);
	}
}

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;
		pos[x] = p;
	}
	seg1::init();
	LoopR (i,0,n) {
		int l = seg1::getc(pos[i]-k+1, pos[i]);
		int r = seg1::getc(pos[i]+1, pos[i]+k);
		if (l != N)
			A[pos[i]].push_back(pos[l]);
		if (r != N)
			A[pos[i]].push_back(pos[r]);
		seg1::up(pos[i], i);
	}
	//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:60:3: note: in expansion of macro 'Loop'
   60 |   Loop (i,0,z.size()) {
      |   ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6540 KB Output is correct
3 Correct 2 ms 6540 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6540 KB Output is correct
6 Correct 47 ms 10260 KB Output is correct
7 Correct 668 ms 12484 KB Output is correct
8 Execution timed out 4051 ms 12824 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6536 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6536 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 26 ms 6660 KB Output is correct
7 Execution timed out 4070 ms 10136 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6536 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6536 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 26 ms 6660 KB Output is correct
7 Execution timed out 4070 ms 10136 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6536 KB Output is correct
3 Correct 992 ms 10328 KB Output is correct
4 Execution timed out 4018 ms 10740 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 6540 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6560 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 6 ms 6584 KB Output is correct
7 Correct 31 ms 7432 KB Output is correct
8 Correct 55 ms 7440 KB Output is correct
9 Correct 49 ms 7500 KB Output is correct
10 Correct 64 ms 7512 KB Output is correct
11 Correct 42 ms 7436 KB Output is correct
12 Correct 63 ms 7436 KB Output is correct
13 Correct 60 ms 7452 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6496 KB Output is correct
2 Correct 3 ms 6544 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 10 ms 6548 KB Output is correct
6 Execution timed out 4035 ms 11344 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6540 KB Output is correct
3 Correct 2 ms 6540 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6540 KB Output is correct
6 Correct 47 ms 10260 KB Output is correct
7 Correct 668 ms 12484 KB Output is correct
8 Execution timed out 4051 ms 12824 KB Time limit exceeded
9 Halted 0 ms 0 KB -