QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#140400#6568. Space Alignmentsmosp#WA 1ms3544kbC++203.5kb2023-08-15 21:00:272023-08-15 21:00:29

Judging History

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

  • [2023-08-15 21:00:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3544kb
  • [2023-08-15 21:00:27]
  • 提交

answer

#include <bits/stdc++.h>  
using namespace std;
typedef long long ll;


ll n;
vector<ll> indents;
vector<ll> spaces;
vector<ll> tabs;

ll euclid(ll a, ll b, ll &x, ll &y){
    if(!b) return x = 1, y= 0, a;
    ll d = euclid(b, a%b, y, x);
    return y -= a/b*x,d;
}

ll crt(ll a, ll m, ll b, ll n){
    if(n > m) swap(a,b), swap(m,n);
    ll x,y,g = euclid(m,n,x,y);
    assert((a-b)%g==0);
    x = (b-a)%n*x%n/g*m+a;
    return x<0?x + m*n/g:x;
}

ll modpow(ll base, ll exp, ll M){
    ll ans = 1;
    while(exp){
        if(exp%2){
            ans *= base;
            ans %= M;
        }
        exp/=2;
        base *= base;
        base %= M;
    }
    return ans;
}

ll modinv(ll n, ll M){
    return modpow(n, M-2, M);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);


    set<ll> primes;
    for(ll i = 2;i<=50;i++){
        ll p =1;
        for(ll j = 2;j*j<=i;j++)
            if(i%j){
                p = 0;
                break;
            }
        if(p)
            primes.insert(i);
    }

    cin>>n;
    vector<string> arr(n);
    for(ll i =0 ;i<n;i++)
        cin>>arr[i];

    indents.resize(n);
    spaces.resize(n);
    tabs.resize(n);

    ll cur_indent = 0;
    for(ll i = 0;i<n;i++){
        ll tab_count = 0;
        ll space_count = 0;
        ll stack_change = 0;
        for(ll j = 0;j<arr[i].size();j++){
            if(arr[i][j] == 's')
                space_count++;
            else if(arr[i][j] == 't')
                tab_count++;
            else if(arr[i][j] == '{')
                stack_change = 1;
            else 
                stack_change = -1;
        }
        if(stack_change == 1){
            indents[i] = cur_indent;
            cur_indent += stack_change;
        }
        else{
            cur_indent += stack_change;
            indents[i] = cur_indent;
        }
        tabs[i] = tab_count;
        spaces[i] = space_count;
    }
    vector<ll> conditions(50,-1);
    ll ok = 1;

    for(ll i = 0;i<n;i++){
        ll t = tabs[i];
        ll ind = indents[i];
        ll s = spaces[i];
        if(!ind && (t||s)){
            ok = 0;
            break;
        }
        if(!ind){
            continue;
        }
        if(ind == 1)
            continue;
        vector<ll> prime_facts;
        for(auto p: primes)
            if(ind%p==0)
                prime_facts.push_back(p);
        ll md = (1000 * ind - s)%ind;
        for(auto p: prime_facts){
            ll val = md*modinv(t,p);
            if(conditions[p] == -1)
                conditions[p] = val;
            else if(conditions[p] != val){
                ok = 0;
                break;
            }
        }
    }
    ll simp_case =1;
    for(auto i: conditions)
        if(i != -1)
            simp_case = 0;
    if(simp_case){
        cout<<"1\n";
        return 0;
    }
    // for(ll i  =1;i<50;i++)
    //     cout<<i<<" "<<conditions[i]<<endl;

    ll prime_prod = 1;
    ll cur_ans = 1;
    for(auto p: primes){
        if(conditions[p] == -1)
            continue;
        if(prime_prod == 1){
            cur_ans = conditions[p];
            prime_prod *= p;
        }else{
            cur_ans = crt(cur_ans, prime_prod, conditions[p], p);
            prime_prod *= p;
        }
    }
    if(cur_ans)
        cout<<cur_ans<<endl;
    else{
        for(ll i = 0;i<50;i++)
            if(conditions[i] == 0){
                cur_ans += i;
                break;
            }
        cout<<(cur_ans)<<endl;
    }
}

詳細信息

Test #1:

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

input:

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

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3472kb

input:

2
{
}

output:

1

result:

ok single line: '1'

Test #3:

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

input:

4
{
ss{
ss}
}

output:

1

result:

ok single line: '1'

Test #4:

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

input:

4
{
tt{
tt}
}

output:

1

result:

ok single line: '1'

Test #5:

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

input:

4
{
ss{
s}
}

output:

1

result:

wrong answer 1st lines differ - expected: '-1', found: '1'