QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#499951#8509. Expanding STACKS!hhhhyfWA 1ms5824kbC++201.9kb2024-07-31 20:28:152024-07-31 20:28:16

Judging History

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

  • [2024-07-31 20:28:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5824kb
  • [2024-07-31 20:28:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
void print() { cout << '\n'; }
template <typename T, typename...Args>
void print(T t, Args...args) { cout << t << ' '; print(args...); }
using ll = long long;
const int N = 1e6 + 1, inf = 1e9;

int dir[4][2] = {
    {1, 0}, {0, 1}, {-1, 0}, {0, -1}
};

template <typename T> bool chmax(T &x, T y) { if (y > x) { x = y; return true; } return false; }
template <typename T> bool chmin(T &x, T y) { if (y < x) { x = y; return true; } return false; }

template <typename T = int>
vector<T> readVector(int n) {
    vector<T> a(n);
    for(T &x: a) cin >> x;
    return a;
} 

int fa[N], v[N];

int find (int x) {
    if (x == fa[x]) {
        return x;
    }
    int root = fa[x];
    v[x] ^= v[fa[x]];
    return fa[x] = root;
}

bool merge (int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        return v[x] ^ v[y];
    }
    v[fy] = v[x] ^ v[y] ^ 1;
    fa[fy] = fx;
    return true;
}

void solve () {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i ++) {
        fa[i] = i;
    }
    
    vector<int> l(n), r(n);
    
    for (int i = 0; i < 2 * n; i ++) {
        char c;
        int x;
        cin >> c >> x;
        x --;
        if (c == '+') {
            l[x] = i;
        } else {
            r[x] = i;
        }
    }
    
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (l[i] < l[j] && l[j] < r[i] && r[j] > r[i] && !merge(i, j)) {
                cout << '*';
                return;
            }
        }
    }
    for (int i = 0; i < n; i ++) {
        int j = find(i);
        cout << (v[i] == 0 ? 'G' : 'S');
    }
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int t = 1; 
	//cin >> t;
	while(t --) {
	    solve();
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5824kb

input:

2
+2 +1 -1 -2

output:

GG

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 5584kb

input:

2
+1 +2 -1 -2

output:

GS

result:

ok correct

Test #3:

score: 0
Accepted
time: 1ms
memory: 5660kb

input:

3
+1 +2 +3 -1 -2 -3

output:

*

result:

ok correct

Test #4:

score: 0
Accepted
time: 1ms
memory: 5580kb

input:

10
+3 -3 +4 -4 +6 +2 -2 -6 +7 -7 +5 -5 +10 +1 +9 +8 -8 -9 -1 -10

output:

GGGGGGGGGG

result:

ok correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 5636kb

input:

10
+8 -8 +2 +10 -2 -10 +7 -7 +1 -1 +6 -6 +5 +3 +4 +9 -9 -4 -3 -5

output:

GGGGGGGGGS

result:

ok correct

Test #6:

score: 0
Accepted
time: 1ms
memory: 5796kb

input:

42
+26 -26 +12 +8 -12 -8 +30 +5 +22 +3 -3 +2 -30 +10 -10 -2 -22 +23 +39 -39 +17 -17 -23 +38 +24 -24 +27 +29 -29 -27 -38 -5 +37 -37 +21 +16 +28 -28 +6 +40 +14 +19 -19 -14 +11 +35 -35 -11 +4 +25 -25 -4 -40 -6 +13 +20 +1 -1 +33 +34 +7 -7 -34 +41 -41 +36 +31 -31 -36 +42 +32 -32 +15 +18 -18 -15 +9 -9 -42...

output:

GSGGSGGSGGGGGGGGGGGGGSGGGGGGGGGGGGGGGGGGGG

result:

ok correct

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 5588kb

input:

42
+40 +18 +42 +2 +1 +21 +33 -2 +8 -33 -8 +14 -40 +34 +30 +31 -31 -30 +5 -5 +4 -34 +13 +3 -13 -3 -4 +28 -28 +17 -17 +35 +10 -10 +16 +39 +36 +37 -37 -36 -39 +25 +6 +41 -41 +20 +12 +32 -32 -25 -12 -16 -35 +38 -20 -38 -14 +15 -15 +9 +26 +23 -21 -1 +7 -23 +22 +24 -7 -24 -42 -18 -22 -26 -9 -6 +27 +29 -29...

output:

GGSSGGSGGGGSGSGSGGGGSGSGGGGGGGGGSGSGGSGGGS

result:

wrong answer client leaving is not the top of its stack