oj.uz

Submission #769158

# Submission time Handle Problem Language Result Execution time Memory
769158 2023-06-29T09:02:29 Z marvinthang Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 122224 KB 
/*************************************
*    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;

void init(int k, vector <int> r) {
	N = r.size();
	--k;
	vector <vector <int>> adj(N);
	REP(v, N) {
		REP(i, N) if (!r[i]) {
			bool ok = true;
			REP(j, k) if (!r[(i - j - 1 + N) % N]) {
				ok = false;
				break;
			}
			if (ok) {
				REP(j, k) {
					int x = (i - j - 1 + N) % N;
					--r[x];
					if (r[x] >= 0) adj[x].push_back(i);
					x = (i + j + 1) % N;
					if (r[x] >= 0) adj[x].push_back(i);
				}
				r[i] = -1;
				break;
			}
		}
	}
	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 1 ms 212 KB Output is correct
2 Correct 1 ms 340 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 4024 KB Output is correct
7 Correct 207 ms 55064 KB Output is correct
8 Execution timed out 4006 ms 13680 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 283 ms 6104 KB Output is correct
7 Execution timed out 4059 ms 122224 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 283 ms 6104 KB Output is correct
7 Execution timed out 4059 ms 122224 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 62 ms 5416 KB Output is correct
4 Execution timed out 4086 ms 13264 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 10 ms 1236 KB Output is correct
8 Correct 14 ms 1452 KB Output is correct
9 Correct 10 ms 1236 KB Output is correct
10 Correct 16 ms 1416 KB Output is correct
11 Correct 12 ms 1208 KB Output is correct
12 Correct 10 ms 1328 KB Output is correct
13 Correct 20 ms 1864 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 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 4024 KB Output is correct
7 Correct 207 ms 55064 KB Output is correct
8 Execution timed out 4006 ms 13680 KB Time limit exceeded
9 Halted 0 ms 0 KB -