QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#140320 | #6568. Space Alignment | smosp# | WA | 1ms | 3576kb | C++20 | 3.7kb | 2023-08-15 18:03:09 | 2023-08-15 18:03:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll n;
cin>>n;
vector<string> arr(n);
for(ll i =0 ;i<n;i++)
cin>>arr[i];
ll cur_indent = 0;
vector<ll> indents(n);
vector<ll> spaces(n);
vector<ll> tabs(n);
for(ll i = 0;i<n;i++){
ll tab_count = 0;
ll space_count = 0;
ll stack_change = 0;
for(ll j = 0;j<arr[i].size();j++){
if(arr[i][j] == 's')
space_count++;
else if(arr[i][j] == 't')
tab_count++;
else if(arr[i][j] == '{')
stack_change = 1;
else
stack_change = -1;
}
if(stack_change == 1){
indents[i] = cur_indent;
cur_indent += stack_change;
}
else{
cur_indent += stack_change;
indents[i] = cur_indent;
}
tabs[i] = tab_count;
spaces[i] = space_count;
}
// cout<<"indents: ";
// for(auto i: indents)
// cout<<i<<" ";
// cout<<endl;
// cout<<"spaces: ";
// for(auto i: spaces)
// cout<<i<<" ";
// cout<<endl;
// cout<<"tabs: ";
// for(auto i: tabs)
// cout<<i<<" ";
// cout<<endl;
ll ok = 1;
ll ans = INT64_MAX;
for(ll i = 0;i<n;i++){
for(ll j = i + 1;j<n;j++){
// cout<<"i = "<<i<<endl;
// cout<<"j = "<<j<<endl;
// cout<<endl;
ll k_val;
if(indents[i]*tabs[j] == indents[j]*tabs[i]){
// cout<<"IN SPECIAL CASE"<<endl;
if(spaces[i]*tabs[j] == spaces[j]*tabs[i]){
// infinitely many values for this pair
// all values of spaces per tab will satisfy
continue;
}
else{
//no values of spaces per tab will work
ok = 0;
break;
}
}else{
ll numerator = (spaces[i]*tabs[j] - spaces[j]*tabs[i]);
ll denominator = (indents[i]*tabs[j] - indents[j]*tabs[i]);
if(numerator*denominator < 0)
continue;
if(numerator%denominator)
continue;
k_val = numerator/denominator;
// cout<<"k_val = "<<k_val<<endl;
ll ans_val;
if(tabs[j])
ans_val = (indents[j]*k_val - spaces[j])/tabs[j];
else if(tabs[i])
ans_val = (indents[i]*k_val - spaces[i])/tabs[i];
else{
// there is no constraint provided by the above tow
continue;
}
// cout<<"ans_val = "<<ans_val<<endl;
ll ok2 = 1;
for(ll f = 0;f<n;f++){
ll num = indents[f]*k_val - spaces[f];
ll den = tabs[f];
if(den == 0 && num != 0){
ok2 = 0;
break;
}
else if(den == 0 && num == 0){
continue;
}
if((num%den) || (num/den != ans_val)){
ok2 = 0;
break;
}
}
if(ok2){
ans = min(ans, ans_val);
}
}
}
}
if((!ok) || (ans==INT64_MAX)){
cout<<"-1\n";
return 0;
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3492kb
input:
10 { ss{ sts{ tt} t} t{ ss} } { }
output:
2
result:
ok single line: '2'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3576kb
input:
2 { }
output:
-1
result:
wrong answer 1st lines differ - expected: '1', found: '-1'