QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#570151	#6568. Space Alignment	UESTC_DECAYALI^#	AC ✓	0ms	4072kb	C++20	2.6kb	2024-09-17 14:18:26	2024-09-17 14:18:30

Judging History

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

[2024-09-17 14:18:30]
评测

测评结果：AC
用时：0ms
内存：4072kb

查看

[2024-09-17 14:18:26]
提交

answer

#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
const int N=105;
typedef pair <int,int> pi;
int n,a[N],dep[N],stk[N],top,mxdep; pi st[N]; vector <pi> bkt[N]; char s[1005];
inline bool check(CI k)
{
    if (k<=0) return 0;
    static int res[N];
    for (RI i=0;i<=mxdep;++i)
    {
        vector <int> tmp;
        for (auto [x,y]:bkt[i]) tmp.push_back(x+y*k);
        sort(tmp.begin(),tmp.end());
        tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
        if (tmp.size()!=1) return 0;
        res[i]=tmp.back();
    }
    if (mxdep==0) return 1;
    vector <int> tmp;
    for (RI i=1;i<=mxdep;++i)
    tmp.push_back(res[i]-res[i-1]);
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    if (tmp.size()!=1) return 0;
    return tmp.back()>0;
}
int main()
{
    scanf("%d",&n);
    for (RI i=1;i<=n;++i)
    {
        scanf("%s",s+1);
        int len=strlen(s+1); pi cur={0,0};
        for (RI j=1;j<len;++j)
        if (s[j]=='s') ++cur.fi; else ++cur.se;
        st[i]=cur; a[i]=(s[len]=='{'?1:-1);
    }
    for (RI i=1;i<=n;++i)
    {
        if (a[i]==1) stk[++top]=i; else
        {
            int pre=stk[top--];
            dep[i]=dep[pre]=top;
            bkt[top].push_back(st[i]);
            bkt[top].push_back(st[pre]);
            mxdep=max(mxdep,top);
        }
    }
    for (RI i=0;i<=mxdep;++i)
    {
        sort(bkt[i].begin(),bkt[i].end());
        bkt[i].erase(unique(bkt[i].begin(),bkt[i].end()),bkt[i].end());
        if (bkt[i].size()==1) continue;
        auto [a,b]=bkt[i][0]; auto [c,d]=bkt[i][1];
        if ((a==c&&b!=d)||(a!=c&&b==d)) return puts("-1"),0;
        if (abs(c-a)%abs(b-d)!=0) return puts("-1"),0;
        int k=(c-a)/(b-d);
        if (check(k)) return printf("%d",k),0; else return puts("-1"),0;
    }
    if (mxdep==0) return puts("1"),0;
    vector <pi> tmp;
    for (RI i=1;i<=mxdep;++i)
    {
        auto [a,b]=bkt[i-1].back(); auto [c,d]=bkt[i].back();
        tmp.push_back({c-a,d-b});
    }
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    if (tmp.size()==1)
    {
        if (check(1)) return puts("1"),0; else return puts("-1"),0;
    }
    auto [a,b]=tmp[0]; auto [c,d]=tmp[1];
    if ((a==c&&b!=d)||(a!=c&&b==d)) return puts("-1"),0;
    if (abs(c-a)%abs(b-d)!=0) return puts("-1"),0;
    int k=(c-a)/(b-d);
    if (check(k)) return printf("%d",k),0; else return puts("-1"),0;
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3740kb

input:

10
{
ss{
sts{
tt}
t}
t{
ss}
}
{
}

output:

result:

ok single line: '2'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3604kb

input:

2
{
}

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3732kb

input:

4
{
ss{
ss}
}

output:

result:

ok single line: '1'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

4
{
tt{
tt}
}

output:

result:

ok single line: '1'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

4
{
ss{
s}
}

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

4
{
tt{
t}
}

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3728kb

input:

4
{
tt{
s}
}

output:

-1

result:

ok single line: '-1'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3896kb

input:

4
{
tt{
sss}
}

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3792kb

input:

4
{
tt{
ssss}
}

output:

result:

ok single line: '2'

Test #10:

score: 0

Accepted

time: 0ms

memory: 4072kb

input:

6
{
}
{
tt{
ssss}
}

output:

result:

ok single line: '2'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3784kb

input:

100
{
}
{
}
{
t{
ssssssssssssssssssssssssssssssssssss}
t{
t}
t{
tssssssssssssssssssssssssssssssssssss{
tssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss{
tsssssssssssssssssssssssssssssssssssst}
ttssssssssssssssssssssssssssssssssssss{
ssssssssssssssssssssssssssssssssssssssssss...

output:

result:

ok single line: '36'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3812kb

input:

100
{
t{
tssssssssssssssssssss{
ttssssssssssssssssssss{
tsssssssssssssssssssstt{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{
ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...

output:

result:

ok single line: '20'

Test #13:

score: 0

Accepted

time: 0ms

memory: 3808kb

input:

4
{
t{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

result:

ok single line: '999'