QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#124666#6568. Space AlignmentSommohito#WA 1ms3512kbC++203.3kb2023-07-15 13:04:592023-07-15 13:05:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-15 13:05:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3512kb
  • [2023-07-15 13:04:59]
  • 提交

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'