QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114105 | #6568. Space Alignment | UFRJ# | AC ✓ | 1ms | 3556kb | C++20 | 2.7kb | 2023-06-21 00:09:42 | 2023-06-21 00:09:45 |
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;
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;
}
}
}
if(ans == -1) ans = 1;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3516kb
input:
10 { ss{ sts{ tt} t} t{ ss} } { }
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
2 { }
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
4 { ss{ ss} }
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
4 { tt{ tt} }
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
4 { ss{ s} }
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
4 { tt{ t} }
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
4 { tt{ s} }
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
4 { tt{ sss} }
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
4 { tt{ ssss} }
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
6 { } { tt{ ssss} }
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
100 { } { } { t{ ssssssssssssssssssssssssssssssssssss} t{ t} t{ tssssssssssssssssssssssssssssssssssss{ tssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss{ tsssssssssssssssssssssssssssssssssssst} ttssssssssssssssssssssssssssssssssssss{ ssssssssssssssssssssssssssssssssssssssssss...
output:
36
result:
ok single line: '36'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
100 { t{ tssssssssssssssssssss{ ttssssssssssssssssssss{ tsssssssssssssssssssstt{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{ ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...
output:
20
result:
ok single line: '20'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
4 { t{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
999
result:
ok single line: '999'