QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#499951 | #8509. Expanding STACKS! | hhhhyf | WA | 1ms | 5824kb | C++20 | 1.9kb | 2024-07-31 20:28:15 | 2024-07-31 20:28:16 |
Judging History
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