QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112254 | #6568. Space Alignment | ITMO_pengzoo# | AC ✓ | 7ms | 3788kb | C++20 | 4.0kb | 2023-06-10 22:43:57 | 2023-06-10 22:44:00 |
Judging History
answer
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <stdio.h>
#include <bits/stdc++.h>
#ifdef PERVEEVM_LOCAL
#define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
#define debug(x) 238
#endif
#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"
using ll = long long;
using ld = long double;
#ifdef PERVEEVM_LOCAL
std::mt19937 rnd(238);
#else
std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
out << "(" << p.first << ", " << p.second << ")";
return out;
}
template<size_t index, typename T>
std::ostream& print_tuple(std::ostream& out, const T& t) {
if constexpr (index == std::tuple_size<T>::value) {
out << ")";
return out;
} else {
if (index > 0) {
out << ", ";
} else {
out << "(";
}
out << std::get<index>(t);
return print_tuple<index + 1, T>(out, t);
}
}
template<typename ...T>
std::ostream& operator<<(std::ostream& out, const std::tuple<T...>& t) {
return print_tuple<0, std::tuple<T...>>(out, t);
}
template<typename Container, typename = decltype(std::begin(std::declval<Container>()))>
typename std::enable_if<!std::is_same<Container, std::string>::value, std::ostream&>::type
operator<<(std::ostream& out, const Container& container) {
out << "{";
for (auto it = container.begin(); it != container.end(); ++it) {
if (it != container.begin()) {
out << ", ";
}
out << *it;
}
out << "}";
return out;
}
template<typename T>
bool smin(T& a, const T& b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool smax(T& a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
void run() {
fastIO;
int n;
std::cin >> n;
std::vector<std::string> lines(n);
for (int i = 0; i < n; ++i) {
std::cin >> lines[i];
}
std::map<int, std::vector<std::pair<int, int>>> cnt;
int lvl = 0;
for (auto s : lines) {
int cntT = 0, cntS = 0;
for (int i = 0; i < (int)s.size() - 1; ++i) {
if (s[i] == 's') {
++cntS;
} else {
++cntT;
}
}
if (s.back() == '}') {
--lvl;
}
cnt[lvl].push_back(std::make_pair(cntS, cntT));
// std::cout << lvl << ' ' << cntS << ' ' << cntT << std::endl;
if (s.back() == '{') {
++lvl;
}
}
for (int x = 1; x <= 100000; ++x) {
ll fixedI = -1;
bool isBad = false;
for (auto&[k, v] : cnt) {
if (isBad) {
break;
}
for (auto[s, t] : v) {
ll left = s + 1ll * x * t;
if (k == 0 && left > 0) {
isBad = true;
break;
}
if (k == 0) {
continue;
}
if (left % k != 0) {
isBad = true;
break;
}
ll i = left / k;
// debug(left);
// debug(i);
if (fixedI == -1) {
fixedI = i;
} else if (fixedI != i) {
isBad = true;
break;
}
}
}
if (!isBad) {
printf("%d\n", x);
return;
}
}
printf("-1\n");
}
int main(void) {
// freopen(NAME".in", "r", stdin);
// freopen(NAME".out", "w", stdout);
#ifdef PERVEEVM_LOCAL
auto start = std::chrono::high_resolution_clock::now();
#endif
run();
#ifdef PERVEEVM_LOCAL
auto end = std::chrono::high_resolution_clock::now();
std::cerr << "Execution time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms" << std::endl;
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
input:
10 { ss{ sts{ tt} t} t{ ss} } { }
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
2 { }
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
4 { ss{ ss} }
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
4 { tt{ tt} }
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 5ms
memory: 3588kb
input:
4 { ss{ s} }
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
4 { tt{ t} }
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
4 { tt{ s} }
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 7ms
memory: 3556kb
input:
4 { tt{ sss} }
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
4 { tt{ ssss} }
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
6 { } { tt{ ssss} }
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3788kb
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: 3764kb
input:
100 { t{ tssssssssssssssssssss{ ttssssssssssssssssssss{ tsssssssssssssssssssstt{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{ ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...
output:
20
result:
ok single line: '20'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
4 { t{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
999
result:
ok single line: '999'