QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#369524 | #8509. Expanding STACKS! | willow# | WA | 1ms | 5868kb | C++17 | 1.6kb | 2024-03-28 13:39:53 | 2024-03-28 13:39:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1005;
template <typename T> inline void read(T &WOW) {
T x = 0, flag = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') flag = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
WOW = flag * x;
}
int n, L[N], R[N], g[N][N], col[N];
bool Check(int s) {
queue<int> q;
col[s] = 1;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 1; v <= n; ++v) {
if (u == v || g[u][v]) continue;
if (col[v]) {
if (col[u] == col[v]) {
return 0;
}
} else {
col[v] = 3 - col[u];
q.push(v);
}
}
}
return 1;
}
void solve() {
read(n);
for (int i = 1; i <= n * 2; ++i) {
int x; read(x);
if (x > 0) L[x] = i;
else R[-x] = i;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
if (L[i] < L[j] && R[j] < R[i]) {
g[i][j] = g[j][i] = 1;
}
}
}
for (int i = 1; i <= n; ++i) {
if (!col[i]) {
if (!Check(i)) {
puts("*");
return;
}
}
}
for (int i = 1; i <= n; ++i) {
putchar(col[i] == 1? 'G' : 'S');
}
puts("");
}
int main() {
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3528kb
input:
2 +2 +1 -1 -2
output:
GG
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2 +1 +2 -1 -2
output:
GS
result:
ok correct
Test #3:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
3 +1 +2 +3 -1 -2 -3
output:
*
result:
ok correct
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3560kb
input:
10 +3 -3 +4 -4 +6 +2 -2 -6 +7 -7 +5 -5 +10 +1 +9 +8 -8 -9 -1 -10
output:
*
result:
wrong answer team and jury output doesn't agree on whether there's an assignment