QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#707205 | #6568. Space Alignment | tassei903# | AC ✓ | 0ms | 3852kb | C++23 | 3.5kb | 2024-11-03 15:06:48 | 2024-11-03 15:06:48 |
Judging History
answer
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define rep(i, l, r) for (int i = l; i < (r); i++)
#define all(x) begin(x), end(x)
using ll = long long;
using vi = vector<int>;
const ll INF = numeric_limits<ll>::max() / 100;
struct MCMF{
struct edge {
int from, to, rev;
ll cap, cost, flow;
};
int N;
vector<vector<edge>> ed;
vi seen;
vector<ll> dist, pi;
vector<edge*> par;
MCMF(int N) : N(N), ed(N), seen(N), dist(N), pi(N), par(N) {}
void addEdge(int from, int to, ll cap, ll cost) {
if (from == to) return;
ed[from].push_back(edge{ from, to, sz(ed[to]), cap, cost, 0});
ed[to].push_back(edge{to, from, sz(ed[from])-1, 0, -cost, 0});
}
void path(int s) {
fill(all(seen), 0);
fill(all(dist), INF);
dist[s] = 0; ll di;
__gnu_pbds::priority_queue<pair<ll, int>> q;
vector<decltype(q)::point_iterator> its(N);
q.push({0, s});
while (!q.empty()) {
s = q.top().second; q.pop();
seen[s] = 1; di = dist[s] + pi[s];
for (edge& e : ed[s]) if (!seen[e.to]) {
ll val = di - pi[e.to] + e.cost;
if (e.cap - e.flow > 0 && val < dist[e.to]) {
dist[e.to] = val;
par[e.to] = &e;
if (its[e.to] == q.end()) {
its[e.to] = q.push({-dist[e.to], e.to});
}
else {
q.modify(its[e.to], {-dist[e.to], e.to});
}
}
}
}
rep(i,0,N) pi[i] = min(pi[i] + dist[i], INF);
}
pair<ll, ll> maxflow(int s, int t) {
ll totflow = 0, totcost = 0;
while (path(s), seen[t]) {
ll fl = INF;
for (edge* x = par[t]; x; x = par[x->from]) {
fl = min(fl, x->cap - x->flow);
}
totflow += fl;
for(edge* x = par[t]; x; x = par[x->from]) {
x->flow += fl;
ed[x->to][x->rev].flow -= fl;
}
}
rep(i, 0, N)for(edge& e : ed[i]) totcost += e.cost * e.flow;
return {totflow, totcost/2};
}
};
bool is_prime(ll x) {
for (ll a = 2; a * a <= x; a++) {
if (x % a == 0)return 0;
}
return 1;
}
const unsigned long long inf = 1e18 + 2;
unsigned long long safe_pow(unsigned long long x, int e) {
unsigned long long a = 1;
rep(_, 0, e) {
if (a > inf / x)return -1;
a *= x;
}
return a;
}
int main() {
auto indent = [&](string s)->pair<int, int> {
int res = 0, res2 = 0;
rep(i, 0, sz(s) - 1) {
if (s[i] == 's')res++;
else res2 += 1;
}
return {res, res2};
};
int n;
cin >> n;
vector<int> x(n), y(n);
vector<string> s(n);
rep(i, 0, n) {
cin >> s[i];
tie(x[i], y[i]) = indent(s[i]);
}
// cout << "YES" << endl;
rep(i, 1, 1001) {
auto check = [&]->bool{
int d = 0, k = -1;
rep(j, 0, n) {
if (s[j].back() == '}')d -= 1;
if (d == 0) {
if (x[j] + y[j] > 0) return 0;
}
else if (k == -1) {
if ((x[j] + y[j] * i) % d)return 0;
else k = (x[j] + y[j]* i) / d;
}
else {
if (x[j] + y[j] * i != d * k)return 0;
}
if (s[j].back() == '{') {
d += 1;
}
}
return 1;
};
if (check()){
cout << i << endl;
return 0;
}
}
cout << -1 << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3788kb
input:
10 { ss{ sts{ tt} t} t{ ss} } { }
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
2 { }
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 { ss{ ss} }
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
4 { tt{ tt} }
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
4 { ss{ s} }
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
4 { tt{ t} }
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
4 { tt{ s} }
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
4 { tt{ sss} }
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
4 { tt{ ssss} }
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
6 { } { tt{ ssss} }
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3620kb
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: 3668kb
input:
100 { t{ tssssssssssssssssssss{ ttssssssssssssssssssss{ tsssssssssssssssssssstt{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstt{ ttsssssssssssssssssssstssssssssssssssssssssssssssssssssssssssss{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstsssssssss...
output:
20
result:
ok single line: '20'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
4 { t{ sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
999
result:
ok single line: '999'