#ifndef hwe
#include "sphinx.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))
#define Int __int128
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;
template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <class T>
void remove_duplicate(vector<T> &ve) {
sort (ve.begin(), ve.end());
ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
return rng() % r;
}
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;
#ifdef hwe
int perform_experiment(vector<int> E);
#endif
namespace sub12 {
vector<int> find_colours(int n, vector<int> X, vector<int> Y) {
vector<int> g(n, -1);
for (int i = 0; i < n; ++i) {
for (int c = 0; c < n; ++c) {
vector<int> E(n, c); E[i] = -1;
int foo = perform_experiment(E);
if (foo == 1) {
g[i] = c;
break;
}
}
}
return g;
}
}
namespace sub3 {
vector<int> find_colours(int n, vector<int> X, vector<int> Y) {
int m = X.size(); vector<int> g(n, 0), ans(n, 0);
for (int i = 0; i < m; ++i) {
vector<int> E(n, n); E[i] = E[i + 1] = -1;
int foo = perform_experiment(E);
if (foo == 1 + (i > 0) + (i + 1 < m)) g[i + 1] = g[i];
else g[i + 1] = !g[i];
}
return g;
for (int l = 0, r = 0; l < n; l = r + 1) {
while (r + 1 < n && g[r + 1] == g[l]) ++r;
auto check = [&](int mid) {
int pmid = l + 2 * mid + 1, expect = 2 * (mid + 1) + (pmid < r);
vector<int> E(n, -1);
for (int i = 0; i <= mid; ++i) E[l + 2 * i + 1] = i;
int foo = perform_experiment(E);
return foo != expect;
};
int low = 0, high = (r - l - 1) / 2, colour = -1;
while (low <= high) {
int mid = low + high >> 1;
if (check(mid)) high = (colour = mid) - 1;
else low = mid + 1;
}
assert(colour != -1);
for (int i = l; i <= r; ++i) ans[i] = colour;
}
// for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
// if (ans[i] == ans[j]) {
// assert(g[i] == g[j]);
// }
// }
return ans;
}
}
vector<int> find_colours(int n, vector<int> X, vector<int> Y) {
if (n <= 50) return sub12::find_colours(n, X, Y);
int m = X.size();
if (m == n - 1) return sub3::find_colours(n, X, Y);
}
#ifdef hwe
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cerr << '\n'; return 0;
}
#endif
Compilation message
sphinx.cpp: In function 'std::vector<int> sub3::find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:117:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
117 | int mid = low + high >> 1;
| ~~~~^~~~~~
sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:141:1: warning: control reaches end of non-void function [-Wreturn-type]
141 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
#experiments: 6 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
#experiments: 2 |
2 |
Correct |
1 ms |
336 KB |
#experiments: 3 |
3 |
Correct |
1 ms |
336 KB |
#experiments: 3 |
4 |
Correct |
1 ms |
336 KB |
#experiments: 4 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
#experiments: 6 |
2 |
Correct |
1 ms |
336 KB |
#experiments: 2 |
3 |
Correct |
1 ms |
336 KB |
#experiments: 3 |
4 |
Correct |
1 ms |
336 KB |
#experiments: 3 |
5 |
Correct |
1 ms |
336 KB |
#experiments: 4 |
6 |
Correct |
24 ms |
336 KB |
#experiments: 1250 |
7 |
Correct |
20 ms |
336 KB |
#experiments: 785 |
8 |
Correct |
33 ms |
336 KB |
#experiments: 1613 |
9 |
Correct |
29 ms |
336 KB |
#experiments: 1353 |
10 |
Correct |
21 ms |
336 KB |
#experiments: 1138 |
11 |
Correct |
20 ms |
336 KB |
#experiments: 978 |
12 |
Correct |
30 ms |
336 KB |
#experiments: 1278 |
13 |
Correct |
29 ms |
336 KB |
#experiments: 1275 |
14 |
Correct |
14 ms |
336 KB |
#experiments: 750 |
15 |
Correct |
21 ms |
336 KB |
#experiments: 920 |
16 |
Correct |
27 ms |
336 KB |
#experiments: 1361 |
17 |
Correct |
19 ms |
336 KB |
#experiments: 1109 |
18 |
Correct |
25 ms |
336 KB |
#experiments: 1506 |
19 |
Correct |
26 ms |
336 KB |
#experiments: 1280 |
20 |
Correct |
24 ms |
336 KB |
#experiments: 1376 |
21 |
Correct |
26 ms |
336 KB |
#experiments: 1275 |
22 |
Correct |
4 ms |
336 KB |
#experiments: 196 |
23 |
Correct |
4 ms |
336 KB |
#experiments: 150 |
24 |
Correct |
9 ms |
336 KB |
#experiments: 312 |
25 |
Correct |
13 ms |
336 KB |
#experiments: 650 |
26 |
Correct |
20 ms |
336 KB |
#experiments: 966 |
27 |
Correct |
19 ms |
336 KB |
#experiments: 1071 |
28 |
Correct |
25 ms |
336 KB |
#experiments: 1208 |
29 |
Correct |
31 ms |
336 KB |
#experiments: 1179 |
30 |
Correct |
30 ms |
336 KB |
#experiments: 1209 |
31 |
Correct |
20 ms |
336 KB |
#experiments: 1187 |
32 |
Correct |
32 ms |
336 KB |
#experiments: 1417 |
33 |
Correct |
27 ms |
336 KB |
#experiments: 1470 |
34 |
Correct |
28 ms |
336 KB |
#experiments: 1275 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
#experiments: 2 |
2 |
Correct |
1 ms |
336 KB |
#experiments: 3 |
3 |
Correct |
1 ms |
336 KB |
#experiments: 3 |
4 |
Correct |
1 ms |
336 KB |
#experiments: 4 |
5 |
Correct |
24 ms |
336 KB |
#experiments: 1250 |
6 |
Correct |
20 ms |
336 KB |
#experiments: 785 |
7 |
Correct |
33 ms |
336 KB |
#experiments: 1613 |
8 |
Correct |
29 ms |
336 KB |
#experiments: 1353 |
9 |
Correct |
21 ms |
336 KB |
#experiments: 1138 |
10 |
Correct |
20 ms |
336 KB |
#experiments: 978 |
11 |
Correct |
30 ms |
336 KB |
#experiments: 1278 |
12 |
Correct |
29 ms |
336 KB |
#experiments: 1275 |
13 |
Partially correct |
8 ms |
336 KB |
Partially correct |
14 |
Partially correct |
8 ms |
336 KB |
Partially correct |
15 |
Partially correct |
8 ms |
336 KB |
Partially correct |
16 |
Partially correct |
7 ms |
336 KB |
Partially correct |
17 |
Partially correct |
7 ms |
336 KB |
Partially correct |
18 |
Partially correct |
7 ms |
336 KB |
Partially correct |
19 |
Partially correct |
8 ms |
336 KB |
Partially correct |
20 |
Partially correct |
8 ms |
336 KB |
Partially correct |
21 |
Partially correct |
10 ms |
336 KB |
Partially correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
#experiments: 2 |
2 |
Correct |
1 ms |
336 KB |
#experiments: 3 |
3 |
Correct |
1 ms |
336 KB |
#experiments: 3 |
4 |
Correct |
1 ms |
336 KB |
#experiments: 4 |
5 |
Correct |
14 ms |
336 KB |
#experiments: 750 |
6 |
Correct |
21 ms |
336 KB |
#experiments: 920 |
7 |
Correct |
27 ms |
336 KB |
#experiments: 1361 |
8 |
Correct |
19 ms |
336 KB |
#experiments: 1109 |
9 |
Correct |
25 ms |
336 KB |
#experiments: 1506 |
10 |
Correct |
26 ms |
336 KB |
#experiments: 1280 |
11 |
Correct |
24 ms |
336 KB |
#experiments: 1376 |
12 |
Correct |
26 ms |
336 KB |
#experiments: 1275 |
13 |
Runtime error |
14 ms |
1944 KB |
Execution killed with signal 6 |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
#experiments: 6 |
2 |
Correct |
1 ms |
336 KB |
#experiments: 2 |
3 |
Correct |
1 ms |
336 KB |
#experiments: 3 |
4 |
Correct |
1 ms |
336 KB |
#experiments: 3 |
5 |
Correct |
1 ms |
336 KB |
#experiments: 4 |
6 |
Correct |
24 ms |
336 KB |
#experiments: 1250 |
7 |
Correct |
20 ms |
336 KB |
#experiments: 785 |
8 |
Correct |
33 ms |
336 KB |
#experiments: 1613 |
9 |
Correct |
29 ms |
336 KB |
#experiments: 1353 |
10 |
Correct |
21 ms |
336 KB |
#experiments: 1138 |
11 |
Correct |
20 ms |
336 KB |
#experiments: 978 |
12 |
Correct |
30 ms |
336 KB |
#experiments: 1278 |
13 |
Correct |
29 ms |
336 KB |
#experiments: 1275 |
14 |
Correct |
14 ms |
336 KB |
#experiments: 750 |
15 |
Correct |
21 ms |
336 KB |
#experiments: 920 |
16 |
Correct |
27 ms |
336 KB |
#experiments: 1361 |
17 |
Correct |
19 ms |
336 KB |
#experiments: 1109 |
18 |
Correct |
25 ms |
336 KB |
#experiments: 1506 |
19 |
Correct |
26 ms |
336 KB |
#experiments: 1280 |
20 |
Correct |
24 ms |
336 KB |
#experiments: 1376 |
21 |
Correct |
26 ms |
336 KB |
#experiments: 1275 |
22 |
Correct |
4 ms |
336 KB |
#experiments: 196 |
23 |
Correct |
4 ms |
336 KB |
#experiments: 150 |
24 |
Correct |
9 ms |
336 KB |
#experiments: 312 |
25 |
Correct |
13 ms |
336 KB |
#experiments: 650 |
26 |
Correct |
20 ms |
336 KB |
#experiments: 966 |
27 |
Correct |
19 ms |
336 KB |
#experiments: 1071 |
28 |
Correct |
25 ms |
336 KB |
#experiments: 1208 |
29 |
Correct |
31 ms |
336 KB |
#experiments: 1179 |
30 |
Correct |
30 ms |
336 KB |
#experiments: 1209 |
31 |
Correct |
20 ms |
336 KB |
#experiments: 1187 |
32 |
Correct |
32 ms |
336 KB |
#experiments: 1417 |
33 |
Correct |
27 ms |
336 KB |
#experiments: 1470 |
34 |
Correct |
28 ms |
336 KB |
#experiments: 1275 |
35 |
Partially correct |
8 ms |
336 KB |
Partially correct |
36 |
Partially correct |
8 ms |
336 KB |
Partially correct |
37 |
Partially correct |
8 ms |
336 KB |
Partially correct |
38 |
Partially correct |
7 ms |
336 KB |
Partially correct |
39 |
Partially correct |
7 ms |
336 KB |
Partially correct |
40 |
Partially correct |
7 ms |
336 KB |
Partially correct |
41 |
Partially correct |
8 ms |
336 KB |
Partially correct |
42 |
Partially correct |
8 ms |
336 KB |
Partially correct |
43 |
Partially correct |
10 ms |
336 KB |
Partially correct |
44 |
Runtime error |
14 ms |
1944 KB |
Execution killed with signal 6 |
45 |
Halted |
0 ms |
0 KB |
- |