oj.uz

Submission #800167

# Submission time Handle Problem Language Result Execution time Memory
800167 2023-08-01T11:10:02 Z becaido Comparing Plants (IOI20_plants) C++17
19 / 100
 4000 ms 27820 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "plants.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;

int n, k;
int a[SIZE], p[SIZE];
vector<int> adj[SIZE];
vector<pair<int, int>> g[SIZE];

int cnt[SIZE], pre[SIZE];
int sum(int l, int r) {
    if (l <= r) return pre[r] - (l ? pre[l - 1] : 0);
    return sum(l, n - 1) + sum(0, r);
}
void init(int _k, vector<int> r) {
    n = r.size();
    k = _k;
    FOR (i, 0, n - 1) a[i] = r[i], p[i] = -1;
    if (k == 2) {
        FOR (i, 0, n - 1) {
            if (a[i] == 1) adj[i].pb((i + 1) % n);
            else adj[(i + 1) % n].pb(i);
        }
        int sz = 0;
        FOR (i, 0, n - 1) if (adj[i].size() == 2) {
            for (int x : adj[i]) {
                int cnt = 0;
                g[i].pb(sz, cnt++);
                while (adj[x].size()) {
                    g[x].pb(sz, cnt++);
                    x = adj[x][0];
                }
                g[x].pb(sz, cnt++);
                sz++;
            }
        }
        return;
    }
    fill(cnt, cnt + n, k - 1);
    FOR (i, 0, n - 1) {
        FOR (j, 0, n - 1) pre[j] = (j ? pre[j - 1] : 0) + (p[j] == -1 && a[j] == cnt[j]);
        FOR (j, 0, n - 1) if (p[j] == -1 && a[j] == cnt[j]) {
            int l = j - k + 1, r = j - 1;
            if (l < 0) l += n;
            if (r < 0) r += n;
            if (sum(l, r) == 0) {
                p[j] = i;
                if (l < r) FOR (k, l, r) cnt[k]--;
                else {
                    FOR (k, l, n - 1) cnt[k]--;
                    FOR (k, 0, r) cnt[k]--;
                }
                break;
            }
        }
    }
}

int compare_plants(int x, int y) {
	if (k == 2) {
        for (auto [gx, px] : g[x]) for (auto [gy, py] : g[y]) if (gx == gy) {
            return px < py ? -1 : 1;
        }
        return 0;
	}
	return p[x] < p[y] ? -1 : 1;
}

/*
in1
4 3 2
0 1 1 2
0 2
1 2
out1
1
-1

in2
4 2 2
0 1 0 1
0 3
1 3
out2
1
0
*/

#ifdef WAIMAI
int main() {
    int n, k, q;
    vector<int> r;
    vector<int> x;
    vector<int> y;
    vector<int> answer;
	assert(scanf("%d%d%d", &n, &k, &q) == 3);
	r.resize(n);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		int value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	return 0;
}
#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 9752 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 48 ms 12440 KB Output is correct
7 Correct 54 ms 14032 KB Output is correct
8 Correct 86 ms 27308 KB Output is correct
9 Correct 89 ms 27596 KB Output is correct
10 Correct 91 ms 27820 KB Output is correct
11 Correct 84 ms 27596 KB Output is correct
12 Correct 84 ms 27696 KB Output is correct
13 Correct 83 ms 27660 KB Output is correct
14 Correct 83 ms 27596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9696 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9604 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 84 ms 12568 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 10 ms 9684 KB Output is correct
10 Correct 82 ms 12592 KB Output is correct
11 Correct 73 ms 12452 KB Output is correct
12 Correct 71 ms 12716 KB Output is correct
13 Correct 84 ms 12596 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9696 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9604 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 84 ms 12568 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 10 ms 9684 KB Output is correct
10 Correct 82 ms 12592 KB Output is correct
11 Correct 73 ms 12452 KB Output is correct
12 Correct 71 ms 12716 KB Output is correct
13 Correct 84 ms 12596 KB Output is correct
14 Correct 1110 ms 12912 KB Output is correct
15 Execution timed out 4070 ms 16688 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9636 KB Output is correct
3 Correct 54 ms 14304 KB Output is correct
4 Execution timed out 4057 ms 16692 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 9752 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 48 ms 12440 KB Output is correct
7 Correct 54 ms 14032 KB Output is correct
8 Correct 86 ms 27308 KB Output is correct
9 Correct 89 ms 27596 KB Output is correct
10 Correct 91 ms 27820 KB Output is correct
11 Correct 84 ms 27596 KB Output is correct
12 Correct 84 ms 27696 KB Output is correct
13 Correct 83 ms 27660 KB Output is correct
14 Correct 83 ms 27596 KB Output is correct
15 Correct 5 ms 9696 KB Output is correct
16 Correct 7 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 6 ms 9604 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 7 ms 9684 KB Output is correct
21 Correct 84 ms 12568 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 10 ms 9684 KB Output is correct
24 Correct 82 ms 12592 KB Output is correct
25 Correct 73 ms 12452 KB Output is correct
26 Correct 71 ms 12716 KB Output is correct
27 Correct 84 ms 12596 KB Output is correct
28 Correct 1110 ms 12912 KB Output is correct
29 Execution timed out 4070 ms 16688 KB Time limit exceeded
30 Halted 0 ms 0 KB -