QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#111399	#6568. Space Alignment	hos_lyric	AC ✓	7ms	3796kb	C++14	2.7kb	2023-06-06 22:55:29	2023-06-06 22:55:32

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-06-06 22:55:32]
评测

测评结果：AC
用时：7ms
内存：3796kb

查看

[2023-06-06 22:55:29]
提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


constexpr int LIM = 2'100'000;

int N;
char A[110][1010];

int main() {
  for (; ~scanf("%d", &N); ) {
    for (int i = 0; i < N; ++i) {
      scanf("%s", A[i]);
    }
    
    vector<int> D(N, 0), S(N, 0), T(N, 0);
    {
      int now = 0;
      for (int i = 0; i < N; ++i) {
        D[i] = now;
        for (int j = 0; A[i][j]; ++j) {
          switch (A[i][j]) {
            case 's': ++S[i]; break;
            case 't': ++T[i]; break;
            case '{': ++now; break;
            case '}': --now; break;
            default: assert(false);
          }
        }
        chmin(D[i], now);
      }
    }
// cerr<<"D = "<<D<<endl;
// cerr<<"S = "<<S<<endl;
// cerr<<"T = "<<T<<endl;
    
    bool zero = true;
    for (int i = 0; i < N; ++i) if (D[i] == 0) {
      zero = zero && (S[i] == 0 && T[i] == 0);
    }
    
    Int ans = -1;
    if (zero) {
      int im = -1;
      for (int i = 0; i < N; ++i) if (D[i] == 1) {
        im = i;
        break;
      }
      if (~im) {
        for (Int x = 1; x <= LIM; ++x) {
          const Int y = S[im] + T[im] * x;
// if(x<=10)cerr<<x<<" "<<y<<endl;
          bool ok = true;
          for (int i = 0; i < N; ++i) {
            if (S[i] + T[i] * x != D[i] * y) {
              ok = false;
              break;
            }
          }
          if (ok) {
            ans = x;
            break;
          }
        }
      } else {
        ans = 1;
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3700kb

input:

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

output:

result:

ok single line: '2'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3696kb

input:

2
{
}

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 2ms

memory: 3696kb

input:

4
{
ss{
ss}
}

output:

result:

ok single line: '1'

Test #4:

score: 0

Accepted

time: 2ms

memory: 3636kb

input:

4
{
tt{
tt}
}

output:

result:

ok single line: '1'

Test #5:

score: 0

Accepted

time: 6ms

memory: 3568kb

input:

4
{
ss{
s}
}

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0

Accepted

time: 6ms

memory: 3636kb

input:

4
{
tt{
t}
}

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0

Accepted

time: 7ms

memory: 3692kb

input:

4
{
tt{
s}
}

output:

-1

result:

ok single line: '-1'

Test #8:

score: 0

Accepted

time: 6ms

memory: 3684kb

input:

4
{
tt{
sss}
}

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0

Accepted

time: 2ms

memory: 3684kb

input:

4
{
tt{
ssss}
}

output:

result:

ok single line: '2'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

6
{
}
{
tt{
ssss}
}

output:

result:

ok single line: '2'

Test #11:

score: 0

Accepted

time: 2ms

memory: 3756kb

input:

100
{
}
{
}
{
t{
ssssssssssssssssssssssssssssssssssss}
t{
t}
t{
tssssssssssssssssssssssssssssssssssss{
tssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss{
tsssssssssssssssssssssssssssssssssssst}
ttssssssssssssssssssssssssssssssssssss{
ssssssssssssssssssssssssssssssssssssssssss...

output:

result:

ok single line: '36'

Test #12:

score: 0

Accepted

time: 2ms

memory: 3796kb

input:

100
{
t{
tssssssssssssssssssss{
ttssssssssssssssssssss{
tsssssssssssssssssssstt{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{
ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...

output:

result:

ok single line: '20'

Test #13:

score: 0

Accepted

time: 1ms

memory: 3632kb

input:

4
{
t{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

result:

ok single line: '999'