QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#413054 | #6568. Space Alignment | Lspeed# | AC ✓ | 83ms | 4080kb | C++20 | 2.8kb | 2024-05-17 01:24:45 | 2024-05-17 01:24:45 |
Judging History
answer
#include<bits/stdc++.h>
#define x first
#define y second
#define eb emplace_back
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define sz(x) (int)(x).size()
#define make_unique(x) sort(all(x)), (x).erase(unique(all(x)), (x).end())
using namespace std;
typedef long long i64;
//typedef __int128 i128;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<i64> vl;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef tuple<int,int,int> iii;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
int readInt() { int a; scanf("%d",&a); return a; }
i64 readLong() { i64 a; scanf("%lld",&a); return a; }
char readChar() { char a; scanf(" %c",&a); return a; }
double readDouble() { double a; scanf(" %lf",&a); return a; }
void readString(char *s) { scanf(" %s",s); }
const int mod = 998244353;
int add(int a, int b) { return ((a+=b)>=mod) ? a-mod:a; }
int mul(int a, int b) { return a*1ll*b%mod; }
int pw(int a, int b) {
int ans = 1, res = a;
for(int i = 1; i <= b; i*=2, res=mul(res,res)) {
if(i&b) {
ans = mul(ans, res);
}
}
return ans;
}
const int N = 105;
int val[N];
char str[N][1005];
int len[N];
int space[N], tab[N];
int main() {
int n = readInt();
int cur = 0;
bool notab = true;
FOR(i,1,n) {
readString(str[i]);
len[i] = strlen(str[i]);
if(str[i][len[i]-1] == '{') {
val[i] = cur;
cur += 1;
} else {
cur -= 1;
val[i] = cur;
}
FOR(j,0,len[i]-2) {
if(str[i][j] == 's') space[i] += 1;
else {
tab[i] += 1;
notab = false;
}
}
//printf("cur %d, space %d, tab %d\n",val[i],space[i],tab[i]);
}
FOR(i,1,n) {
if(val[i] == 0) {
if(tab[i] != 0 || space[i] != 0) {
return !printf("-1\n");
}
} else {
if(tab[i] == 0) {
if(space[i]%val[i] != 0) {
return !printf("-1\n");
}
}
}
}
//puts("pass");
int best = (1<<30);
bool okay = false;
FOR(k, 1, 1000000) {
set<int> ans;
bool good = true;
FOR(i, 1, n) {
if(tab[i] == 0) {
if(space[i] != k*val[i]) {
good = false;
break;
}
} else {
// solve
if((k*val[i]-space[i])%tab[i] != 0) {
good = false;
break;
}
if((k*val[i]-space[i]) <= 0) {
good = false;
break;
}
ans.insert((k*val[i]-space[i])/tab[i]);
}
}
if (!good) {
//if(k==2) printf("wtf\n");
continue;
}
if(sz(ans) > 1) {
continue;
}
if(*ans.begin() > 0) best = min(best, *ans.begin());
okay = true;
}
if(notab && okay) {
printf("1\n");
return 0;
}
if(best == (1<<30)) printf("-1\n");
else printf("%d\n",best);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 4080kb
input:
10 { ss{ sts{ tt} t} t{ ss} } { }
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 4ms
memory: 3708kb
input:
2 { }
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 4ms
memory: 3696kb
input:
4 { ss{ ss} }
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 12ms
memory: 3772kb
input:
4 { tt{ tt} }
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 4ms
memory: 3660kb
input:
4 { ss{ s} }
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 21ms
memory: 3716kb
input:
4 { tt{ t} }
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 12ms
memory: 3992kb
input:
4 { tt{ s} }
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 12ms
memory: 3768kb
input:
4 { tt{ sss} }
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 12ms
memory: 3800kb
input:
4 { tt{ ssss} }
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 13ms
memory: 3872kb
input:
6 { } { tt{ ssss} }
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 22ms
memory: 3888kb
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: 83ms
memory: 3896kb
input:
100 { t{ tssssssssssssssssssss{ ttssssssssssssssssssss{ tsssssssssssssssssssstt{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{ ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...
output:
20
result:
ok single line: '20'
Test #13:
score: 0
Accepted
time: 19ms
memory: 3768kb
input:
4 { t{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
999
result:
ok single line: '999'