QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#363180 | #8509. Expanding STACKS! | ucup-team3113# | WA | 1ms | 3832kb | C++20 | 2.1kb | 2024-03-23 19:18:33 | 2024-03-23 19:18:33 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound
using namespace std;
const int inf = 1e18;
void p(auto A){
for(auto e : A)cout << e << ' ';
cout << '\n';
}
void solve(){
int n; cin >> n;
vector<int>A(2*n);
for(int i = 0; i< 2*n; i++)cin >> A[i];
auto gen = []()->pair<int, vector<int>>{
vector<int>ret;
int num = 10;
for(int i = 1; i<= num; i++)ret.pb(i);
for(int i = 1; i<= num; i++)ret.pb(-i);
random_shuffle(all(ret));
for(int i = 1; i<= num; i++){
int p1, p2;
for(int j = 0; j< ret.size(); j++){
if(ret[j] == i)p1 = j;
if(ret[j] == -i)p2 = j;
}
if(p2 < p1)swap(ret[p2], ret[p1]);
}
return {ret.size()/2, ret};
};
//auto[n, A] = gen();
vector<int>out(n+1);
for(int i = 0; i< 2*n; i++)if(A[i] < 0)out[abs(A[i])] = i;
vector<int>G, S;
G.pb(2*n+5);
S.pb(2*n+5);
vector<char>ans(n+1);
for(int i = 0; i< 2*n; i++){
if(A[i] < 0){
//assert(G.back() == i || S.back() == i);
if(G.back() == i)G.pop_back();
if(S.back() == i)S.pop_back();
}else{
int t = out[A[i]];
if( t > G.back() && t > S.back()){
cout << '*';
return;
}
if(t < G.back() && t < S.back()){
if(G.back() > S.back()){
ans[A[i]] = 'S';
S.pb(t);
}else{
ans[A[i]] = 'G';
G.pb(t);
}
}else{
if(G.back() < S.back()){
ans[A[i]] = 'S';
S.pb(t);
}else{
ans[A[i]] = 'G';
G.pb(t);
}
}
}
}
vector<int> s1, s2;
for(auto e : A){
if(e< 0){
if(s1.size() && s1.back() == -e)s1.pop_back();
else if(s2.size() && s2.back() == -e)s2.pop_back();
else assert(false);
}else{
if(ans[e] == 'G')s1.pb(e);
else s2.pb(e);
}
}
for(int i = 1; i<= n; i++)cout << ans[i];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
//cin >> t;
while(t--)solve();
}
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3632kb
input:
2 +2 +1 -1 -2
output:
GG
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
2 +1 +2 -1 -2
output:
GS
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
3 +1 +2 +3 -1 -2 -3
output:
*
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3784kb
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: 3832kb
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: 3756kb
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:
GSGGSGGSGSGGGGGGSGGGGSSSGGSGSGGGGGGGGSSGGG
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3520kb
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:
SGSGSGSGGSGGGSSSSSGGSGGGSGGSGSSSSSSSSSSGSS
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
42 +29 +6 +7 +2 -7 -2 +23 -23 -6 -29 +19 -19 +16 +8 -16 -8 +32 -32 +3 +37 +17 -17 -37 -3 +22 -22 +18 +1 +40 +36 -1 -36 -40 -18 +9 -9 +30 +25 -25 +14 +39 +5 +20 -5 +12 -39 +28 +10 -14 +24 -24 +35 +15 -15 +41 -30 +33 -33 -41 -35 -10 -28 -12 +21 +38 -38 -21 +11 +13 -13 +4 +42 +27 +34 -34 +31 -31 +26 -2...
output:
GSGSGGGSGSSSSGGGGGGSSGGGGSSSGGSGSSSSGSGSSS
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
100 +39 -39 +4 +71 -71 +53 -53 +46 -46 -4 +91 -91 +97 -97 +6 -6 +54 -54 +76 +35 -35 +50 +89 -89 +98 -50 -76 -98 +34 +55 +95 -34 +36 -36 +73 -95 -55 +18 +47 +20 +30 +33 -30 -33 +80 -73 +51 -51 -80 -20 +69 +77 -69 +85 +62 +84 -84 -77 +48 +49 -49 +1 -1 -48 +19 -19 -62 -85 +41 +16 -16 -41 +63 +2 -2 +65 ...
output:
SSGGGGSSGSGSGSGSGSSSGSGSGSGGGGGSSGGSSGGGSGGGGGSSSGSGGGSSSGGGGSSGSSGGSGGGGGSGGGSSGGSGSGGGGGGGGGSGGSSG
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
100 +5 -5 +61 +48 +60 +69 +7 -7 -69 -60 +45 -45 -48 -61 +68 +4 +82 +57 -57 +12 -12 +22 +46 -46 -22 +14 +30 -30 +47 -47 -14 +94 -94 -82 +44 +27 -27 -44 +86 -86 -4 +50 +15 -15 -50 -68 +58 -58 +28 +83 -83 -28 +53 +1 +56 -56 +67 +13 +73 +87 +19 +65 +18 -18 +17 -17 +89 +62 -62 -89 +72 -72 +25 -25 -65 +98...
output:
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
100 +96 +64 -64 +41 +11 +62 +18 +25 +3 +26 -26 -3 +22 +61 +59 +73 -59 -73 -61 -62 +20 -41 -20 +46 -46 -22 +2 +10 -10 -2 -25 -18 +9 -9 -11 +60 +33 +97 +38 -38 +5 -5 -97 +81 +29 -29 -81 +92 +1 +52 -52 +87 +19 -19 +90 -90 -87 -1 -92 -33 -60 -96 +47 +6 +72 -72 +79 +98 +45 -45 +23 -23 -98 +35 -35 +27 -27...
output:
GSGGGGGGSSSGGGGGGSGSGSGGSGGGGGGGGGGGGGGGGGGGGSGGGGGGGGGGGGGGGGGGGGGGGGGGSGGGGGGGGGGGGGGGGGGGGGGGGGGG
result:
ok correct
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 3588kb
input:
171 +118 +125 +156 +76 +123 +61 +107 +15 +160 -15 -107 -160 +98 +127 -127 +152 -61 -123 +48 +139 +86 -86 +43 +129 +164 +167 +6 +9 +137 +20 +16 -20 -16 +11 +12 +133 +24 -24 -137 -133 +81 +71 +88 +142 -142 +105 -88 +93 +33 -33 -105 +85 +64 -64 +150 +5 -150 +121 -85 +1 -121 +41 -5 +53 +67 +3 -3 +72 +10...
output:
*
result:
wrong answer team and jury output doesn't agree on whether there's an assignment