QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#707205#6568. Space Alignmenttassei903#AC ✓0ms3852kbC++233.5kb2024-11-03 15:06:482024-11-03 15:06:48

Judging History

你现在查看的是最新测评结果

  • [2024-11-03 15:06:48]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3852kb
  • [2024-11-03 15:06:48]
  • 提交

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'