QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #411270 | #6568. Space Alignment | DanielChang | AC ✓ | 0ms | 3752kb | C++17 | 1.9kb | 2024-05-15 10:58:32 | 2024-05-15 10:58:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<array<int,3>> v(n);
int dd=0;
set<int> res;
for(auto &[s, t, x] : v){
s=0, t=0, x=0;
string a;
cin >> a;
if(a.back() == '{'){
x = dd++;
}
else{
x = --dd;
}
for(char c : a){
if(c == 's') s++;
if(c == 't') t++;
}
// cout << s << ' ' << t << ' ' << x << endl;
}
bool ok = 1;
for(int i=0; i<n; i++){
auto [s1, t1, x1] = v[i];
if(x1 == 0){
if(t1 || s1) ok = 0;
continue;
}
if(!t1 && !s1){
ok = 0;
}
if(t1 == 0 && x1){
if(s1 % x1) ok = 0;
// res2.insert(s1 / x1);
}
for(int j=i+1; j<n; j++){
auto [s3, t3, x3] = v[i];
auto [s2, t2, x2] = v[j];
if(x2 == 0) continue;
s3 *= x2; t3 *= x2;
s2 *= x3; t2 *= x3;
// s1 + t1 * T == s2 + t2 * T
if((t3 == t2) != (s3 == s2)){
ok = 0;
}
else if(t2 != t3){
int dt = t3 - t2, ds = s2 - s3;
assert(dt && ds);
int d = ds / dt;
if(dt * d != ds){
// cout << "bad: " << i << " " << j << endl;
ok = 0;
}
else{
// cout << i << " " << j << " -> " << d << endl;
res.insert(d);
}
}
}
}
// cout << "res: ";
// for(auto d : res) cout << d << ' ';
// cout << endl;
// cout << "ok: " << ok << endl;
if(!ok || res.size() > 1 || (res.size()==1 && *begin(res) < 1)){
cout << -1;
}
else if(res.empty()){
cout << 1;
}
else{
cout << *begin(res);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
10
{
ss{
sts{
tt}
t}
t{
ss}
}
{
}
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
2
{
}
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
4
{
ss{
ss}
}
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
4
{
tt{
tt}
}
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
4
{
ss{
s}
}
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4
{
tt{
t}
}
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4
{
tt{
s}
}
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4
{
tt{
sss}
}
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
4
{
tt{
ssss}
}
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
6
{
}
{
tt{
ssss}
}
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3748kb
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: 0ms
memory: 3512kb
input:
100
{
t{
tssssssssssssssssssss{
ttssssssssssssssssssss{
tsssssssssssssssssssstt{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{
ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...
output:
20
result:
ok single line: '20'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
4
{
t{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
999
result:
ok single line: '999'