QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#114101#6568. Space AlignmentUFRJ#WA 1ms3464kbC++202.0kb2023-06-20 23:36:562023-06-20 23:36:57

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-20 23:36:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3464kb
  • [2023-06-20 23:36:56]
  • 提交

answer

#include "bits/stdc++.h"

using lint = int64_t;
using ld = long double;

using namespace std;

const lint inf = lint(1e18) + 1;
int n;

struct Line
{
  int d, s, t;
};


int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int d = 0;
  cin >> n;
  vector<Line> v;
  for(int i = 0; i < n; i++) {
    string tmp;
    cin >> tmp;
    if(tmp.back() == '}') d--;

    int cntS = 0, cntT = 0;
    for(auto &i : tmp) {
      if(i == 's') cntS++;
      if(i == 't') cntT++;
    }

    if(d != 0 and (cntS + cntT) > 0) v.push_back({d, cntS, cntT});

    if(tmp.back() == '{') d++;
  }

  if(n == 2) {
    cout << 0 << endl;
    return 0;
  }

  // for(auto &i : v) {
  //   cout << i.d << " = " << i.s << " + " << i.t << endl; 
  // }

  lint ans = inf;
  for(int i = 0; i < v.size(); i++) {
    ld si = (ld) v[i].s/v[i].d;
    ld ti = (ld) v[i].t/v[i].d;
    set<lint> possible;
    if(ti == 0) {
      possible.insert(0);
    }
    for(int j = 0; j < v.size(); j++) {
      if(j == i) continue;
      ld ns = si*v[j].d;
      ld nt = ti*v[j].d;

      ld num = (ns - v[j].s), de = (v[j].t - nt);

      // cout << num << " / " << de << endl;      
      if(de == 0 and num > 0) {
        possible.insert(0);
        continue;
      }

      if(de == 0) continue;

      ld ps = num/de;

      // cout << num << " / " << de << endl;
      if(ps >= 0) possible.insert(ps);
    }
    // cout << "Possible: " << i << "\n";
    // for(auto &i : possible) cout << i << ' ';
    // cout << endl;
    for(auto &x : possible) {
      bool ok = true;
      map<int, int> mp;
      // cout << "Possible: " << x << endl;
      for(auto &eq : v) {
        lint res = eq.s + x*eq.t;
        // cout << eq.d << " " << res << endl;
        if(mp.count(eq.d) and mp[eq.d] != res) {
          ok = false;
          break;
        } 
        mp[eq.d] = res;
      }
      if(ok) ans = min(ans, x);
    }
  }

  if(ans == inf) cout << -1 << endl;
  else cout << ans << endl;

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

2

result:

ok single line: '2'

Test #2:

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

input:

2
{
}

output:

0

result:

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