QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#379673#8509. Expanding STACKS!ucup-team004#WA 1ms5644kbC++201000b2024-04-06 18:14:102024-04-06 18:14:11

Judging History

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

  • [2024-04-06 18:14:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5644kb
  • [2024-04-06 18:14:10]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using namespace std;
const int inf=1e9,N=1005;
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
int n,in[N],out[N],vis[N],e[N][N];
bool bh(int x,int y){
    return in[x]<=in[y]&&out[x]>=out[y];
}
void dfs(int p,int x){
    if(vis[p]!=-1&&vis[p]!=x){
        cout<<"*\n"; exit(0);
    }
    if(vis[p]!=-1)return;
    vis[p]=x;
    For(i,1,n)if(e[i][p])dfs(i,x^1);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin>>n;
    For(i,1,n*2){
        char ch;
        cin>>ch;
        while(ch!='+'&&ch!='-')cin>>ch;
        int x;
        cin>>x;
        if(ch=='+')in[x]=i; else out[x]=i;
    }
    For(i,1,n)For(j,i+1,n)if(!bh(i,j)&&!bh(j,i))e[i][j]=e[j][i]=1;
    //For(i,1,n)cout<<in[i]<<" "<<out[i]<<" "<<e[1][2]<<endl;
    memset(vis,-1,sizeof(vis));
    For(i,1,n)if(vis[i]==-1)dfs(i,0);
    For(i,1,n)if(vis[i])cout<<'S'; else cout<<'G';
    cout<<endl;
    return 0;
}

詳細信息

Test #1:

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

input:

2
+2 +1 -1 -2

output:

GG

result:

ok correct

Test #2:

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

input:

2
+1 +2 -1 -2

output:

GS

result:

ok correct

Test #3:

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

input:

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

output:

*

result:

ok correct

Test #4:

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

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