QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#99476 | #5528. Least Annoying Constructive Problem | willow# | TL | 415ms | 3640kb | C++14 | 882b | 2023-04-22 17:41:51 | 2023-04-22 17:41:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n, vis[505][505], tot, cnte, fa[505];
pair<int, int> pr[250005];
int Get(int x) {
return x == fa[x] ? x : fa[x] = Get(fa[x]);
}
int main() {
srand(unsigned(time(NULL)));
scanf("%d", &n);
for(int i = 1; i <= n; ++ i)
for(int j = i + 1; j <= n; ++ j)
pr[++ cnte] = {i, j};
int f = 0, c = 0;
while(!f) {
f = 1;
++ c;
random_shuffle(pr + 1, pr + cnte + 1);
for(int i = 1; i <= cnte; ++ i) {
for(int j = 1; j <= n; ++ j)
fa[j] = j;
for(int j = 1; j < n; ++ j) {
int w = i + j - 1;
if(w > cnte)
w -= cnte;
int u = Get(pr[w].first), v = Get(pr[w].second);
if(fa[u] != fa[v]) {
fa[u] = v;
continue;
}
f = 0;
break;
}
if(!f)
break;
}
}
for(int i = 1; i <= cnte; ++ i)
printf("%d %d\n", pr[i].first, pr[i].second);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3640kb
input:
3
output:
1 2 2 3 1 3
result:
ok Correct
Test #2:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
4
output:
2 4 1 3 2 3 1 4 3 4 1 2
result:
ok Correct
Test #3:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
5
output:
1 2 2 3 4 5 2 4 1 3 3 4 1 5 2 5 3 5 1 4
result:
ok Correct
Test #4:
score: 0
Accepted
time: 4ms
memory: 3620kb
input:
6
output:
5 6 2 4 3 5 1 5 1 2 2 6 4 5 1 3 4 6 3 6 2 5 2 3 1 4 1 6 3 4
result:
ok Correct
Test #5:
score: 0
Accepted
time: 415ms
memory: 3564kb
input:
7
output:
2 3 1 3 4 7 3 6 5 6 2 4 4 5 1 2 6 7 3 7 1 7 2 5 1 4 2 6 3 5 5 7 1 6 2 7 3 4 1 5 4 6
result:
ok Correct
Test #6:
score: -100
Time Limit Exceeded
input:
8