QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#207987 | #6568. Space Alignment | Thallium54# | AC ✓ | 1ms | 7832kb | C++20 | 1.9kb | 2023-10-09 02:21:59 | 2023-10-09 02:21:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
const int N = 1e5 + 100;
const int inf = 1e9;
const ll mod = 9302023;
int a[N], b[N], d[N];
int n;
string s[N];
inline void check(int x)
{
int k = -1;
for(int i = 0; i < n; i++)
{
if(d[i] == 0 && (x*a[i] + b[i]) != 0)
{
cout << -1 << endl;
exit(0);
}
if(d[i] == 0)
continue;
//cout << i << ' ' << x << ' ' << d[i] << ' ' << k << endl;
// d[i] != 0
if((x*a[i] + b[i])%d[i] != 0)
{
cout << -1 << endl;
exit(0);
}
if(k == -1)
{
k = (x*a[i] + b[i]) / d[i];
continue;
}
if(k != (x*a[i] + b[i]) / d[i])
{
cout << -1 << endl;
exit(0);
}
}
if(k == 0 || x == 0)
cout << -1 << endl;
else
cout << x << endl;
exit(0);
}
int main()
{
cin >> n;
int k = 0;
for(int i = 0; i < n; i++)
{
cin >> s[i];
int m = s[i].size();
if(s[i][m-1] == '}')
k--;
for(int j = 0; j < m-1; j++)
{
if(s[i][j] == 's')
b[i]++;
else
a[i]++;
}
d[i] = k;
if(s[i][m-1] == '{')
k++;
}
for(int i = 0; i < n; i++)
{
if(d[i] == 0)
{
if(b[i] != 0)
{
cout << -1 << endl;
exit(0);
}
if(a[i] != 0)
{
check(0);
}
continue;
}
for(int j = i+1; j < n; j++)
{
if(d[j] == 0)
{
if(b[j] != 0)
{
cout << -1 << endl;
exit(0);
}
if(a[j] != 0)
{
check(0);
}
continue;
}
int A = a[i]*d[j], B = b[i]*d[j];
int A2 = a[j]*d[i], B2 = b[j]*d[i];
if(A == A2 && B == B2)
continue;
if(A == A2)
{
cout << -1 << endl;
exit(0);
}
check((B2-B)/(A-A2));
}
}
cout << 1 << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6844kb
input:
10 { ss{ sts{ tt} t} t{ ss} } { }
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7208kb
input:
2 { }
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 6780kb
input:
4 { ss{ ss} }
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 6848kb
input:
4 { tt{ tt} }
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 6848kb
input:
4 { ss{ s} }
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 7272kb
input:
4 { tt{ t} }
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7508kb
input:
4 { tt{ s} }
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 1ms
memory: 7724kb
input:
4 { tt{ sss} }
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 6868kb
input:
4 { tt{ ssss} }
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 1ms
memory: 6804kb
input:
6 { } { tt{ ssss} }
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 1ms
memory: 7832kb
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: 1ms
memory: 7044kb
input:
100 { t{ tssssssssssssssssssss{ ttssssssssssssssssssss{ tsssssssssssssssssssstt{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{ ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...
output:
20
result:
ok single line: '20'
Test #13:
score: 0
Accepted
time: 1ms
memory: 6796kb
input:
4 { t{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
999
result:
ok single line: '999'