QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#369524#8509. Expanding STACKS!willow#WA 1ms5868kbC++171.6kb2024-03-28 13:39:532024-03-28 13:39:54

Judging History

你现在查看的是最新测评结果

  • [2024-03-28 13:39:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5868kb
  • [2024-03-28 13:39:53]
  • 提交

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