QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114103#6568. Space AlignmentUFRJ#WA 1ms3504kbC++202.6kb2023-06-21 00:05:132023-06-21 00:05:31

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-21 00:05:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3504kb
  • [2023-06-21 00:05:13]
  • 提交

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;
  vector<vector<pair<int, int>>>e(n);
  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++;
    }
    e[d].push_back({cntS, cntT});
    if(!d && (cntS || cntT)){
      cout<<"-1\n";
      return 0;
    }

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

  if(n == 2) {
    cout<<"1\n";
    return 0;
  }

  int as = -1, at = -1, k = 1;

  int ans = -1;
  for(int i=1;i<n;i++){
    for(auto [bs, bt] : e[i]){
      if(as == -1){
        as = bs;
        at = bt;
        k = i;
      }
      else{
        if(i * as == bs * k && i * at == bt * k) continue;
        int right = (bs * k - as * i);
        int d = (at * i - bt * k);
        if(!d || right % d || (ans != -1 && right / d != ans) || right / d < 0){
          cout<<"-1\n";
          return 0;
        }
        ans = right / d;
      }
    }
  }
  cout<<ans<<"\n";
  /* 
  // 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;
}

详细

Test #1:

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

input:

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

output:

2

result:

ok single line: '2'

Test #2:

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

input:

2
{
}

output:

1

result:

ok single line: '1'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3476kb

input:

4
{
ss{
ss}
}

output:

-1

result:

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