oj.uz

Submission #800132

# Submission time Handle Problem Language Result Execution time Memory
800132 2023-08-01T10:45:40 Z becaido Comparing Plants (IOI20_plants) C++17
5 / 100
 123 ms 29824 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];
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++;
            }
        }
    }
}

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;
	}
}

/*
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

Compilation message

plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
   65 | }
      | ^

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 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9640 KB Output is correct
6 Correct 50 ms 13384 KB Output is correct
7 Correct 56 ms 16124 KB Output is correct
8 Correct 86 ms 29392 KB Output is correct
9 Correct 123 ms 29720 KB Output is correct
10 Correct 85 ms 29716 KB Output is correct
11 Correct 86 ms 29724 KB Output is correct
12 Correct 88 ms 29716 KB Output is correct
13 Correct 99 ms 29816 KB Output is correct
14 Correct 97 ms 29824 KB Output is correct

Subtask #2
0 / 14.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 Incorrect 5 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 Incorrect 5 ms 9684 KB Output isn't correct
4 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 Incorrect 7 ms 9684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 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 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9640 KB Output is correct
6 Correct 50 ms 13384 KB Output is correct
7 Correct 56 ms 16124 KB Output is correct
8 Correct 86 ms 29392 KB Output is correct
9 Correct 123 ms 29720 KB Output is correct
10 Correct 85 ms 29716 KB Output is correct
11 Correct 86 ms 29724 KB Output is correct
12 Correct 88 ms 29716 KB Output is correct
13 Correct 99 ms 29816 KB Output is correct
14 Correct 97 ms 29824 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9636 KB Output is correct
17 Incorrect 5 ms 9684 KB Output isn't correct
18 Halted 0 ms 0 KB -