QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#363180#8509. Expanding STACKS!ucup-team3113#WA 1ms3832kbC++202.1kb2024-03-23 19:18:332024-03-23 19:18:33

Judging History

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

  • [2024-03-23 19:18:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3832kb
  • [2024-03-23 19:18:33]
  • 提交

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