QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#354819#6568. Space Alignmentkevinshan#WA 1ms3624kbC++172.8kb2024-03-16 03:15:162024-03-16 03:15:16

Judging History

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

  • [2024-03-16 03:15:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3624kb
  • [2024-03-16 03:15:16]
  • 提交

answer

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

#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define For(i,a) FOR(i,0,a)
#define pi pair<int,int>
#define trav(a,b) for(auto& a:b)

map<int,set<pi>> M;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }
    int n;cin>>n;
    int curDepth=0, mxDep=0;
    For(i,n) {
        int s=0,t=0;
        string S;cin>>S;
        For(j,S.size()) {
            if(S[j]=='s') {
                s++;
            } else if(S[j]=='t') {
                t++;
            } else {
                if(S[j]=='}') {
                    curDepth--;
                }
                // cout << i << " " << s << " A " << t << curDepth << endl;
                mxDep = max(mxDep, curDepth);
                M[curDepth].insert({s,t});
                if(S[j]=='{') {
                    curDepth++;
                } else {
                    // curDepth--;
                }
            }
        }
        
    }
    // trav(x,M) {
    //     cout << x.f;
    //     trav(y,x.s) {
    //         cout << y.f << " " << y.s << " B ";
    //     }
    //     cout << endl;
    // }

    int tri = -1;
    For(i,n)if(M[i].size()>1) {
        pi A = *M[i].begin();
        pi B = *(++M[i].begin());
        if (tri==-1 && B.s!=A.s) {
            tri = (B.f-A.f)/(A.s-B.s);
        }
    }
    // cout << "A " << tri << endl;
    if(tri==-1) {
        set<pi> diffs;
        For(i,mxDep-1) {
            assert(M[i].size()>0 && M[i+1].size()>0);
            pi A = *M[i].begin();
            pi B = *M[i+1].begin();
            diffs.insert({B.f-A.f,B.s-A.s});
        }
        if (diffs.size()<=1) {
            cout << 1 << endl;
            return 0;
        }
        pi A = *diffs.begin();
        pi B = *(++diffs.begin());
        tri = (B.f-A.f)/(A.s-B.s);
    }
    bool works = true;
    if(tri<=0) {
        cout << -1 << endl;
        return 0;
    }
    assert(tri!=-1);
    
    vector<int> v;
    For(i,mxDep) {
        int need = -1;
        trav(x, M[i]){
            int sum = x.f + tri*x.s;
            if (need==-1) {
                need=sum;
            } else if(need!=sum) {
                works = false;
            }
        }
        assert(need!=-1);
        v.pb(need);
    }
    if(v.size()>1) {
        int K = v[1]-v[0];
        For(i,v.size()-1) if(v[i+1]-v[i]!=K) {
            works = false;
        }
    }

    if(!works) {
        cout << -1 << endl;
    } else {
        cout << tri << endl;
    }
    

    
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

2

result:

ok single line: '2'

Test #2:

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

input:

2
{
}

output:

1

result:

ok single line: '1'

Test #3:

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

input:

4
{
ss{
ss}
}

output:

1

result:

ok single line: '1'

Test #4:

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

input:

4
{
tt{
tt}
}

output:

1

result:

ok single line: '1'

Test #5:

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

input:

4
{
ss{
s}
}

output:

1

result:

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