QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#711206 | #9241. Sphinx | ivan_alexeev# | 22.5 | 50ms | 4832kb | C++23 | 3.7kb | 2024-11-05 02:25:18 | 2024-11-05 02:25:18 |
Judging History
answer
#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
#ifdef lisie_bimbi
#else
#define endl '\n'
#endif
typedef long long ll;
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
const ll inf = 1'000'000'000;
#ifdef lisie_bimbi
namespace {
const int CALLS_CNT_LIMIT = 2750;
int calls_cnt;
int N, M;
std::vector<int> C;
std::vector<int> X, Y;
std::vector<std::vector<int>> adj;
void quit(const char* message) {
printf("%s\n", message);
exit(0);
}
int count_components(const std::vector<int>& S) {
int components_cnt = 0;
std::vector<bool> vis(N, false);
for (int i = 0; i < N; i++) {
if (vis[i])
continue;
components_cnt++;
std::queue<int> q;
vis[i] = true;
q.push(i);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int nxt : adj[cur])
if (!vis[nxt] && S[nxt] == S[cur]) {
vis[nxt] = true;
q.push(nxt);
}
}
}
return components_cnt;
}
} // namespace
int perform_experiment(std::vector<int> E) {
calls_cnt++;
if (calls_cnt > CALLS_CNT_LIMIT)
quit("Too many calls");
if ((int)E.size() != N)
quit("Invalid argument");
for (int i = 0; i < N; i++)
if (!(-1 <= E[i] && E[i] <= N))
quit("Invalid argument");
std::vector<int> S(N);
for (int i = 0; i < N; i++)
S[i] = (E[i] == -1 ? C[i] : E[i]);
return count_components(S);
}
#endif
int CNT = 0;
int perform_experiment1(std::vector<int> E) {
CNT++;
if(CNT > 2750){
while(true){
}
}
return perform_experiment(E);
}
vector<vector<int>> v;
vector<int> used;
void dfs(int u){
used[u] = 1;
for(auto i : v[u]){
if(!used[i]){
dfs(i);
}
}
}
int n;
vector<int> c;
int get(int u){
int l = 0, r = n;
while(l + 1 != r){
int m = (l + r) / 2;
vector<int> e(n, n);
int now = l;
for(int i = 0; now < m; i++){
if(i == u){
continue;
}
e[i] = now++;
}
e[u] = -1;
int x = perform_experiment1(e);
if(x == m - l + 1){
r = m;
}else{
l = m;
}
}
return l;
}
vector<int> find_colours(int N, vector<int> x, vector<int> y){
n = N;
v.resize(n);
for(int i = 0; i < x.size(); i++){
v[x[i]].push_back(y[i]);
v[y[i]].push_back(x[i]);
}
c.resize(n);
for(int i = 0; i < n; i++){
c[i] = get(i);
}
return c;
}
#ifdef lisie_bimbi
int main() {
#ifdef lisie_bimbi
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
cin.tie(nullptr)->sync_with_stdio(false);
#endif
assert(2 == scanf("%d%d", &N, &M));
C.resize(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &C[i]));
X.resize(M), Y.resize(M);
for (int j = 0; j < M; j++)
assert(2 == scanf("%d%d", &X[j], &Y[j]));
fclose(stdin);
adj.assign(N, std::vector<int>());
for (int j = 0; j < M; j++) {
adj[X[j]].push_back(Y[j]);
adj[Y[j]].push_back(X[j]);
}
calls_cnt = 0;
std::vector<int> G = find_colours(N, X, Y);
int L = G.size();
printf("%d %d\n", L, calls_cnt);
for (int i = 0; i < L; i++)
printf("%s%d", (i == 0 ? "" : " "), G[i]);
printf("\n");
fclose(stdout);
return 0;
}
#endif
/*
signed main(){
#ifdef lisie_bimbi
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
cin.tie(nullptr)->sync_with_stdio(false);
#endif
int t = 1;
cin >> t;
while(t--){
solve();
}
return 0;
}
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1.5
Acceptable Answer
Test #1:
score: 1.5
Acceptable Answer
time: 1ms
memory: 3728kb
input:
1978433568 2 1 0 1 1978433568 1 1978433568 1
output:
877694080 -1 0 877694080 0 -1 877694081 1 1
result:
points 0.50 points 0.5
Test #2:
score: 1.5
Acceptable Answer
time: 1ms
memory: 3776kb
input:
1978433568 2 1 0 1 1978433568 1 1978433568 2
output:
877694080 -1 0 877694080 0 -1 877694081 1 0
result:
points 0.50 points 0.5
Test #3:
score: 1.5
Acceptable Answer
time: 0ms
memory: 4060kb
input:
1978433568 2 1 0 1 1978433568 2 1978433568 1
output:
877694080 -1 0 877694080 0 -1 877694081 0 1
result:
points 0.50 points 0.5
Test #4:
score: 1.5
Acceptable Answer
time: 1ms
memory: 3776kb
input:
1978433568 2 1 0 1 1978433568 2 1978433568 2
output:
877694080 -1 0 877694080 0 -1 877694081 0 0
result:
points 0.50 points 0.5
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
50%
Acceptable Answer
Test #5:
score: 0
Wrong Answer
time: 3ms
memory: 3728kb
input:
1978433568 50 49 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 19784335...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 877694080 -1 25 26 27 28 29 30 31 32 33 34 35 36 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50...
result:
wrong answer Vertices 23 and 24 do have the same color, but they do not in returned answer
Subtask #3:
score: 0
Wrong Answer
Test #34:
score: 0
Wrong Answer
time: 30ms
memory: 3824kb
input:
1978433568 250 249 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 ...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
result:
wrong answer Vertices 7 and 8 do have the same color, but they do not in returned answer
Subtask #4:
score: 21
Accepted
Test #43:
score: 21
Accepted
time: 50ms
memory: 4548kb
input:
1978433568 250 31125 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 5...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
result:
ok #experiments: 2000
Test #44:
score: 21
Accepted
time: 35ms
memory: 4624kb
input:
1978433568 250 31125 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 5...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
result:
ok #experiments: 1967
Test #45:
score: 21
Accepted
time: 48ms
memory: 4572kb
input:
1978433568 250 31125 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 5...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
result:
ok #experiments: 2000
Test #46:
score: 21
Accepted
time: 38ms
memory: 4544kb
input:
1978433568 250 31125 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 5...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
result:
ok #experiments: 2000
Test #47:
score: 21
Accepted
time: 29ms
memory: 4564kb
input:
1978433568 250 31125 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 5...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
result:
ok #experiments: 1987
Test #48:
score: 21
Accepted
time: 39ms
memory: 4796kb
input:
1978433568 250 31125 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 5...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
result:
ok #experiments: 1990
Test #49:
score: 21
Accepted
time: 32ms
memory: 4832kb
input:
1978433568 250 31125 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 5...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
result:
ok #experiments: 1992
Test #50:
score: 21
Accepted
time: 41ms
memory: 4540kb
input:
1978433568 250 31125 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 5...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
result:
ok #experiments: 2000
Test #51:
score: 21
Accepted
time: 36ms
memory: 4560kb
input:
1978433568 250 31125 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 5...
output:
877694080 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
result:
ok #experiments: 1994
Subtask #5:
score: 0
Skipped
Dependency #1:
50%
Acceptable Answer
Dependency #2:
0%