QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #112388 | #6568. Space Alignment | ckiseki# | AC ✓ | 2ms | 3392kb | C++20 | 2.8kb | 2023-06-11 15:36:32 | 2023-06-11 15:36:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int cnt = sizeof...(T);
(..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L)
cerr << (f++ ? ", " : "") << *L;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif
[[noreturn]] void bad() {
cout << -1 << '\n';
exit(0);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n; cin >> n;
vector<pair<pair<int, int>, int>> v(n);
int cur = 0;
for (auto &[lhs, rhs] : v) {
int s = 0, t = 0, l = cur;
string o;
cin >> o;
for (auto c : o) {
if (c == 's') s++;
else if (c == 't') t++;
else if (c == '{') cur++;
else cur--;
}
if (o.back() == '}') l--;
lhs = {l, -t};
rhs = s;
}
auto par = [&](int a1, int b1, int a2, int b2) -> optional<int> {
if (a2 == 0) {
if (a1 == 0)
return 0;
return nullopt;
}
if (a1 % a2 != 0)
return nullopt;
int d = a1 / a2;
if (b2 * d != b1)
return nullopt;
return d;
};
for (int i = 0; i < n; ++i) {
auto [ai, bi] = v[i].first;
int ci = v[i].second;
if (ai == 0 and bi == 0 and ci == 0) continue;
for (int j = i + 1; j < n; ++j) {
auto [aj, bj] = v[j].first;
int cj = v[j].second;
if (aj == 0 and bj == 0 and cj == 0) continue;
if (auto d = par(ai, bi, aj, bj); d) {
if (ci != *d * cj) bad();
continue;
}
int a2b1 = aj * bi;
int a1b2 = ai * bj;
int a2c1 = aj * ci;
int a1c2 = ai * cj;
if ((a2c1 - a1c2) % (a2b1 - a1b2) == 0) {
int y = (a2c1 - a1c2) / (a2b1 - a1b2);
if (y <= 0) bad();
int a1x = ci - bi * y;
if (a1x % ai == 0) {
int x = a1x / ai;
if (x <= 0) bad();
for (auto [ab, c] : v) {
if (ab.first * x + ab.second * y != c)
bad();
}
cout << y << '\n';
return 0;
} else bad();
} else bad();
}
}
cout << 1 << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3344kb
input:
10
{
ss{
sts{
tt}
t}
t{
ss}
}
{
}
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3320kb
input:
2
{
}
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3340kb
input:
4
{
ss{
ss}
}
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3324kb
input:
4
{
tt{
tt}
}
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
4
{
ss{
s}
}
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3392kb
input:
4
{
tt{
t}
}
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3316kb
input:
4
{
tt{
s}
}
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3332kb
input:
4
{
tt{
sss}
}
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
4
{
tt{
ssss}
}
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3292kb
input:
6
{
}
{
tt{
ssss}
}
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3352kb
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: 3356kb
input:
100
{
t{
tssssssssssssssssssss{
ttssssssssssssssssssss{
tsssssssssssssssssssstt{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{
ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...
output:
20
result:
ok single line: '20'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3312kb
input:
4
{
t{
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
999
result:
ok single line: '999'