QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114101 | #6568. Space Alignment | UFRJ# | WA | 1ms | 3464kb | C++20 | 2.0kb | 2023-06-20 23:36:56 | 2023-06-20 23:36:57 |
Judging History
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'