QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#124666 | #6568. Space Alignment | Sommohito# | WA | 1ms | 3512kb | C++20 | 3.3kb | 2023-07-15 13:04:59 | 2023-07-15 13:05:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#ifdef APURBA
#include "DEBUG_TEMPLATE.h"
#else
#define HERE
#define debug(args...)
#endif
#define ALL(x) x.begin(),x.end()
int gcd(int a,int b)
{
if(a<b)swap(a,b);
if(b==0)return a;
if(a%b==0)return b;
return gcd(b,a%b);
}
int lcm(int a,int b)
{
return(a*b)/gcd(a,b);
}
ll egcd(int a, int b, ll &x,ll &y)
{
if(a==0){
x=0,y=1;
return b;
}
ll x1,y1,d=egcd(b%a,a,x1,y1);
x=y1-(b/a)*x1;
y=x1;
return d;
}
const int N = 1004;
string s[N];
void no()
{
cout<<"-1\n";
exit(0);
}
void TEST_CASES()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s[i];
}
vector<array<ll,3> > vs;
int k = 0;
for(int i=0;i<n;i++)
{
char c = s[i].back();
int a = 0;
for(char c: s[i]) a+='s'==c;
int b = 0;
for(char c: s[i]) b+='t'==c;
if(c=='}')
k--;
if(k==0)
{
debug(a,b);
if(a or b)
no();
}
else
vs.push_back({a,b,k});
if(c == '{')
{
k++;
}
}
assert(k==0);
debug(k);
if(vs.empty())
cout<<"1\n";
else
{
auto x = vs[0];
int i=1;
ll ii = -1;
ll xx = -1;
for(;i<vs.size();i++)
{
auto [a1,b1,c1] = x;
auto [a2,b2,c2] = vs[i];
if(a1*b2 == a2*b1 and a1*c2 == a2*c1 and b1*c2 == b2*c1)
continue;
ll niche = -c1*b2+c2*b1;
if(niche == 0) no();
ll upore_i = -a1*b2+a2*b1;
ll upore_x = c1*a2-c2*a1;
if(abs(upore_i) % abs(niche) != 0) no();
if(abs(upore_x) % abs(niche) != 0) no();
ii = upore_i/niche;
xx = upore_x / niche;
if(ii<=0) no();
if(xx<0) no();
i++;
break;
}
while(i<vs.size())
{
auto [a2,b2,c2] = vs[i];
if(a2+b2*xx != c2*ii) no();
i++;
}
debug(ii,xx);
if(ii==-1)
{
auto [a1,b1,c1] = x;
if(b1 == 0)
{
if(a1 % c1 != 0)
no();
cout<<"0\n";
}
else
{
ll g = __gcd(c1,b1);
if(a1%g != 0)
no();
egcd(c1,b1,ii,xx);
ii*=a1/g;
xx*=a1/g;
ll k = min((ll)(ceil(ii*1.0/(b1/g))) - 1 , (ll)(ceil(-xx*1.0/(c1/g)))-1);
xx+=k*c1/g;
ii-=k*b1/g;
assert(c1*ii+xx*b1 == a1);
assert(-xx>0);
cout<<-xx<<"\n";
}
}
else cout<<xx<<"\n";
}
}
/*
*/
int32_t main()
{
#ifndef APURBA
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
//freopen("input.txt","r",stdin);
//freopen("out1.txt","w",stdout);
int t=1;
//cin>>t;
while(t--)
{
TEST_CASES();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3428kb
input:
10 { ss{ sts{ tt} t} t{ ss} } { }
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
2 { }
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3512kb
input:
4 { ss{ ss} }
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'