QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #140326 | #6568. Space Alignment | smosp# | WA | 1ms | 3492kb | C++20 | 4.5kb | 2023-08-15 18:23:53 | 2023-08-15 18:23:56 |
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(tabs[i] == 0){
if(indents[i] && spaces[i]%indents[i] || !indents[i] && spaces[i]){
ok = 0;
// cout<<"CASE1"<<endl;
break;
}
if(indents[i])
k_val = spaces[i]/indents[i];
}
if(tabs[j]==0){
if(indents[j] && spaces[j]%indents[j] || !indents[j] && spaces[j]){
ok = 0;
// cout<<"CASE2"<<endl;
break;
}
if(indents[j])
k_val = spaces[j]/indents[j];
}
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;
// cout<<"CASE3"<<endl;
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{
ans_val = -1;
}
// 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){
ok2 = 0;
break;
}
if((ans_val == -1)){
ans_val = num/den;
continue;;
}
else if(ans_val != num/den){
ok2 =0;break;
}
}
if(ok2){
ans = min(ans, ans_val);
}
}
}
if(ans == INT64_MAX && ok){
cout<<"1\n";
return 0;
}
else 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: 0
Accepted
time: 1ms
memory: 3460kb
input:
2
{
}
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
4
{
ss{
ss}
}
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
4
{
tt{
tt}
}
output:
1
result:
ok single line: '1'
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3460kb
input:
4
{
ss{
s}
}
output:
1
result:
wrong answer 1st lines differ - expected: '-1', found: '1'