QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #490383 | #6568. Space Alignment | SmallAoPigBigPiPig# | AC ✓ | 0ms | 4008kb | C++23 | 2.1kb | 2024-07-25 14:58:11 | 2024-07-25 14:58:11 |
Judging History
answer
#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int ch = 0, f = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
char str[2005];
vector<pair<int, int> > bac[2005];
int ans[2005], n, mxd;
#define fi first
#define se second
inline int checkans(int k){
//cout << "check: " << k << endl;
for(int i = 0; i <= mxd; i++){
ans[i] = bac[i][0].fi + bac[i][0].se * k;
//cout << "?: " << bac[i][0].fi << " " << bac[i][0].se << endl;
for(auto [x, y] : bac[i])
if(ans[i] != x + y * k){
//cout << "!" << i << " " << x << " " << y << " " << ans[i] << endl;
return 0;
}
}
//cout << "OK" << endl;
if(ans[1] <= ans[0]) return 0;
for(int i = 2; i <= mxd; i++){
if(ans[i] - ans[i-1] != ans[1] - ans[0])
return 0;
}
return 1;
}
inline void doit(vector<pair<int, int> > vec){
sort(vec.begin(), vec.end());
for(int i = 1; i < (int) vec.size(); i++)
if(vec[i] != vec[i-1]){
int ds = vec[i].fi - vec[i-1].fi;
int dt = vec[i-1].se - vec[i].se;
//cout << ds << " " << dt << endl;
if(ds <= 0 || dt <= 0 || ds % dt != 0) puts("-1");
else if(checkans(ds / dt)) printf("%d\n", ds / dt);
else puts("-1");
exit(0);
}
}
int main(){
read(n);
if(n == 2) return puts("1"), 0;
scanf("%s", str);
bac[0].push_back(make_pair(0, 0));
for(int i = 1, d = 0; i < n - 1; i++){
scanf("%s", str);
int m = strlen(str), cs = 0, ct = 0;
for(int j = 0; j < m - 1; j++)
if(str[j] == 's') cs++; else ct++;
if(str[m-1] == '{') d++;
bac[d].push_back(make_pair(cs, ct));
mxd = max(mxd, d);
if(str[m-1] == '}') d--;
}
scanf("%s", str);
for(int i = 0; i <= mxd; i++) doit(bac[i]);
vector<pair<int, int> > vec;
for(int i = 1; i <= mxd; i++)
vec.push_back(make_pair(bac[i][0].fi - bac[i-1][0].fi, bac[i][0].se - bac[i-1][0].se));
doit(vec);
puts("1");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4008kb
input:
10
{
ss{
sts{
tt}
t}
t{
ss}
}
{
}
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
2
{
}
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4
{
ss{
ss}
}
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
4
{
tt{
tt}
}
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4
{
ss{
s}
}
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
4
{
tt{
t}
}
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
4
{
tt{
s}
}
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
4
{
tt{
sss}
}
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
4
{
tt{
ssss}
}
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
6
{
}
{
tt{
ssss}
}
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3736kb
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: 3880kb
input:
100
{
t{
tssssssssssssssssssss{
ttssssssssssssssssssss{
tsssssssssssssssssssstt{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{
ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...
output:
20
result:
ok single line: '20'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
4
{
t{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
999
result:
ok single line: '999'