oj.uz

Submission #800149

# Submission time Handle Problem Language Result Execution time Memory
800149 2023-08-01T10:57:01 Z becaido Comparing Plants (IOI20_plants) C++17
5 / 100
 95 ms 33476 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> v[SIZE];
vector<int> adj[SIZE];
vector<pair<int, int>> g[SIZE];

void init(int _k, vector<int> r) {
    n = r.size();
    k = _k;
    FOR (i, 0, n - 1) a[i] = r[i];
    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++;
            }
        }
    }
    FOR (i, 0, n - 1) v[a[i]].pb(i);
    int cnt = 0;
    for (int i = k - 1; i >= 0; i--) if (v[i].size()) {
        sort(v[i].begin(), v[i].end());
        FOR (j, 0, v[i].size() - 1) {
            int last = j ? j - 1 : v[i].size() - 1;
            bool is = 0;
            if (j) is |= v[i][last] + k <= v[i][j];
            else is |= v[i][last] + k < n || (v[i][last] + k) % n <= v[i][j];
            if (is) {
                FOR (k, j, v[i].size() - 1) p[v[i][k]] = cnt++;
                FOR (k, 0, j - 1) p[v[i][k]] = cnt++;
                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 8 ms 14388 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 9 ms 14292 KB Output is correct
5 Correct 9 ms 14352 KB Output is correct
6 Correct 50 ms 17144 KB Output is correct
7 Correct 57 ms 18876 KB Output is correct
8 Correct 91 ms 32932 KB Output is correct
9 Correct 92 ms 33296 KB Output is correct
10 Correct 92 ms 33244 KB Output is correct
11 Correct 95 ms 33476 KB Output is correct
12 Correct 92 ms 33240 KB Output is correct
13 Correct 91 ms 33268 KB Output is correct
14 Correct 90 ms 33284 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 9 ms 14344 KB Output is correct
4 Incorrect 7 ms 14292 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14388 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 9 ms 14292 KB Output is correct
5 Correct 9 ms 14352 KB Output is correct
6 Correct 50 ms 17144 KB Output is correct
7 Correct 57 ms 18876 KB Output is correct
8 Correct 91 ms 32932 KB Output is correct
9 Correct 92 ms 33296 KB Output is correct
10 Correct 92 ms 33244 KB Output is correct
11 Correct 95 ms 33476 KB Output is correct
12 Correct 92 ms 33240 KB Output is correct
13 Correct 91 ms 33268 KB Output is correct
14 Correct 90 ms 33284 KB Output is correct
15 Correct 8 ms 14292 KB Output is correct
16 Correct 8 ms 14380 KB Output is correct
17 Incorrect 8 ms 14392 KB Output isn't correct
18 Halted 0 ms 0 KB -