QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#570145 | #6568. Space Alignment | UESTC_DECAYALI# | RE | 0ms | 4128kb | C++20 | 2.6kb | 2024-09-17 14:14:55 | 2024-09-17 14:14:56 |
Judging History
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=2;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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4128kb
input:
10 { ss{ sts{ tt} t} t{ ss} } { }
output:
2
result:
ok single line: '2'
Test #2:
score: -100
Runtime Error
input:
2 { }