QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#140397 | #6568. Space Alignment | smosp# | WA | 1ms | 3588kb | C++20 | 3.5kb | 2023-08-15 20:59:46 | 2023-08-15 20:59:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
vector<ll> indents;
vector<ll> spaces;
vector<ll> tabs;
ll euclid(ll a, ll b, ll &x, ll &y){
if(!b) return x = 1, y= 0, a;
ll d = euclid(b, a%b, y, x);
return y -= a/b*x,d;
}
ll crt(ll a, ll m, ll b, ll n){
if(n > m) swap(a,b), swap(m,n);
ll x,y,g = euclid(m,n,x,y);
assert((a-b)%g==0);
x = (b-a)%n*x%n/g*m+a;
return x<0?x + m*n/g:x;
}
ll modpow(ll base, ll exp, ll M){
ll ans = 1;
while(exp){
if(exp%2){
ans *= base;
ans %= M;
}
exp/=2;
base *= base;
base %= M;
}
return ans;
}
ll modinv(ll n, ll M){
return modpow(n, M-2, M);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
set<ll> primes;
for(ll i = 2;i<=50;i++){
ll p =1;
for(ll j = 2;j*j<=i;j++)
if(i%j){
p = 0;
break;
}
if(p)
primes.insert(i);
}
cin>>n;
vector<string> arr(n);
for(ll i =0 ;i<n;i++)
cin>>arr[i];
indents.resize(n);
spaces.resize(n);
tabs.resize(n);
ll cur_indent = 0;
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;
}
vector<ll> conditions(50,-1);
ll ok = 1;
for(ll i = 0;i<n;i++){
ll t = tabs[i];
ll ind = indents[i];
ll s = spaces[i];
if(!ind && (t||s)){
ok = 0;
break;
}
if(!ind){
continue;
}
if(ind == 1)
continue;
vector<ll> prime_facts;
for(auto p: primes)
if(ind%p==0)
prime_facts.push_back(p);
ll md = (1000 * ind - s)%ind;
for(auto p: prime_facts){
ll val = md*modinv(t,p);
if(conditions[p] == -1)
conditions[p] = val;
else if(conditions[p] != val){
ok = 0;
break;
}
}
}
ll simp_case =1;
for(auto i: conditions)
if(i != -1)
simp_case = 0;
if(simp_case){
cout<<"1\n";
return 0;
}
// for(ll i =1;i<50;i++)
// cout<<i<<" "<<conditions[i]<<endl;
ll prime_prod = 1;
ll cur_ans = 1;
for(auto p: primes){
if(conditions[p] == -1)
continue;
if(prime_prod == 1){
cur_ans = conditions[p];
prime_prod *= p;
}else{
cur_ans = crt(cur_ans, prime_prod, conditions[p], p);
prime_prod *= p;
}
}
if(cur_ans)
cout<<cur_ans<<endl;
else{
for(ll i = 0;i<50;i++)
if(conditions[i] == 0)
cur_ans += i;
cout<<(cur_ans)<<endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3464kb
input:
10 { ss{ sts{ tt} t} t{ ss} } { }
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
2 { }
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
4 { ss{ ss} }
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3588kb
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'