Submission #769173

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
769173	2023-06-29T09:16:33 Z	marvinthang	Comparing Plants (IOI20_plants)	C++17	25 / 100	4000 ms	56348 KB

plants

/*************************************
*    author: marvinthang             *
*    created: 29.06.2023 15:49:29    *
*************************************/

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

int N;
vector <vector <bool>> visited;

int get_prev(int i, int j) {
	i -= j;
	return i < 0 ? i + N : i;
}

int get_next(int i, int j) {
	i += j;
	return i >= N ? i - N : i;
}

void init(int k, vector <int> r) {
	N = r.size();
	vector <int> h(N);
	--k;
	vector <vector <int>> adj(N);
	REPD(v, N) {
		REP(i, N) if (!r[i]) {
			bool ok = true;
			REP(j, k) if (!r[get_prev(i, j + 1)]) {
				ok = false;
				break;
			}
			if (ok) {
				REP(j, k) --r[get_prev(i, j + 1)];
				r[i] = -1;
				h[i] = v;
				break;
			}
		}
	}
	set <pair <int, int>> left, right;
	REP(i, k) {
		int x = get_prev(0, i + 1);
		left.insert(make_pair(h[x], x));
		x = get_next(0, i + 1);
		right.insert(make_pair(h[x], x));
	}
	REP(i, N) {
		auto it = left.lower_bound(make_pair(h[i], i));
		if (it != left.begin()) adj[i].push_back(prev(it)->se);
		it = right.lower_bound(make_pair(h[i], i));
		if (it != right.begin()) adj[i].push_back(prev(it)->se);
		int x = get_prev(i, k);
		left.erase(make_pair(h[x], x));
		left.insert(make_pair(h[i], i));

		x = get_next(i, 1);
		right.erase(make_pair(h[x], x));
		x = get_next(i, k + 1);
		right.insert(make_pair(h[x], x));

	}

	visited.resize(N, vector<bool>(N));
	REP(i, N) {
		queue <int> q;
		q.push(i);
		visited[i][i] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int v: adj[u]) if (!visited[i][v]) {
				visited[i][v] = 1;
				q.push(v);
			}
		}
	}
}

int compare_plants(int x, int y) {
	if (visited[x][y]) return 1;
	if (visited[y][x]) return -1;
	return 0;
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	39 ms	3020 KB	Output is correct
7	Correct	206 ms	53852 KB	Output is correct
8	Execution timed out	4054 ms	9580 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	296 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	716 KB	Output is correct
7	Correct	240 ms	7316 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	8 ms	724 KB	Output is correct
10	Correct	228 ms	8648 KB	Output is correct
11	Correct	148 ms	8348 KB	Output is correct
12	Correct	146 ms	8660 KB	Output is correct
13	Correct	259 ms	8700 KB	Output is correct

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	296 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	8 ms	716 KB	Output is correct
7	Correct	240 ms	7316 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	8 ms	724 KB	Output is correct
10	Correct	228 ms	8648 KB	Output is correct
11	Correct	148 ms	8348 KB	Output is correct
12	Correct	146 ms	8660 KB	Output is correct
13	Correct	259 ms	8700 KB	Output is correct
14	Execution timed out	4045 ms	56348 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	56 ms	3816 KB	Output is correct
4	Execution timed out	4072 ms	9756 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #5

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	10 ms	1204 KB	Output is correct
8	Correct	10 ms	1208 KB	Output is correct
9	Correct	10 ms	1284 KB	Output is correct
10	Correct	10 ms	1236 KB	Output is correct
11	Correct	10 ms	1200 KB	Output is correct
12	Correct	12 ms	1236 KB	Output is correct
13	Correct	10 ms	1328 KB	Output is correct

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	7 ms	576 KB	Output is correct
6	Execution timed out	4022 ms	10256 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	39 ms	3020 KB	Output is correct
7	Correct	206 ms	53852 KB	Output is correct
8	Execution timed out	4054 ms	9580 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-