Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
ab = input()
for i in range(1, len(ab)):
if ab[i] != '0' and int(ab[:i]) < int(ab[i:]):
print(ab[:i], ab[i:])
break
else:
print(-1)
Idea: BledDest, preparation: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
for _ in range(int(input())):
s = input()
cnt = [0, 0]
for i in range(len(s)):
cnt[int(s[i])] += 1
for i in range(len(s) + 1):
if (i == len(s) or cnt[1 - int(s[i])] == 0):
print(len(s) - i)
break
cnt[1 - int(s[i])] -= 1
Idea: Ferume, preparation: Ferume
Tutorial
Tutorial is loading...
Solution (awoo)
from sys import stdin, stdout
LOG = 30
cnt = [0 for i in range(LOG)]
ans = []
for _ in range(int(stdin.readline())):
t, v = map(int, stdin.readline().split())
if t == 1:
cnt[v] += 1
else:
nw = 0
for i in range(LOG):
r = (v % (2 << i)) // (1 << i)
if r > nw + cnt[i]:
ans.append(0)
break
v -= r
nw = (nw + cnt[i] - r) // 2
else:
ans.append(nw >= (v >> 30))
stdout.write('\n'.join(["YES" if x else "NO" for x in ans]))
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int normalize(long long x) {
x %= MOD;
if (x < 0) x += MOD;
return x;
}
int main() {
int t;
cin >> t;
for (int tc = 0; tc < t; ++tc) {
int n;
cin >> n;
vector <int> a(n);
vector <int> nextMin(n);
vector <int> dpSum(n + 2);
vector <int> dpNext(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
stack <int> stMin;
nextMin[n - 1] = n;
dpSum[n] = 1;
for (int pos = n - 1; pos >= 0; --pos) {
while(!stMin.empty() && a[stMin.top()] > a[pos])
stMin.pop();
nextMin[pos] = stMin.empty() ? n : stMin.top();
stMin.push(pos);
int nxtPos = nextMin[pos];
int dpPos = normalize(dpSum[pos + 1] - dpSum[nxtPos + 1]);
if (nxtPos != n) {
dpPos = normalize(dpPos + dpNext[nxtPos]);
dpNext[pos] = normalize(dpSum[nxtPos] - dpSum[nxtPos + 1] + dpNext[nxtPos]);
}
dpSum[pos] = normalize(dpPos + dpSum[pos + 1]);
//cout << pos << ' ' << nxtPos << ' ' << dpPos << endl;
}
int res = 0;
int mn = a[0];
for(int i = 0; i < n; ++i) {
mn = min(mn, a[i]);
if (a[i] == mn) {
res = normalize(res + dpSum[i] - dpSum[i + 1]);
}
}
cout << res << endl;
}
return 0;
}
Idea: Ferume, preparation: Ferume
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 111;
struct edge
{
int y, c, w, f;
edge() {};
edge(int y, int c, int w, int f) : y(y), c(c), w(w), f(f) {};
};
vector<edge> e;
vector<int> g[N];
int rem(int x)
{
return e[x].c - e[x].f;
}
void add_edge(int x, int y, int c, int w)
{
g[x].push_back(e.size());
e.push_back(edge(y, c, w, 0));
g[y].push_back(e.size());
e.push_back(edge(x, 0, -w, 0));
}
int n, m, s, t, v;
pair<int, long long> MCMF()
{
int flow = 0;
long long cost = 0;
while(true)
{
vector<long long> d(v, (long long)(1e18));
vector<int> p(v, -1);
vector<int> pe(v, -1);
queue<int> q;
vector<bool> inq(v);
q.push(s);
inq[s] = true;
d[s] = 0;
while(!q.empty())
{
int k = q.front();
q.pop();
inq[k] = false;
for(auto ei : g[k])
{
if(rem(ei) == 0) continue;
int to = e[ei].y;
int w = e[ei].w;
if(d[to] > d[k] + w)
{
d[to] = d[k] + w;
p[to] = k;
pe[to] = ei;
if(!inq[to])
{
inq[to] = true;
q.push(to);
}
}
}
}
if(p[t] == -1) break;
flow++;
cost += d[t];
int cur = t;
while(cur != s)
{
e[pe[cur]].f++;
e[pe[cur] ^ 1].f--;
cur = p[cur];
}
}
return make_pair(flow, cost);
}
int get_sum(const vector<int>& v)
{
int sum = 0;
for(auto x : v) sum += x;
return sum;
}
int main()
{
cin >> n >> m;
s = n + m;
t = n + m + 1;
v = n + m + 2;
int sum_matrix = 0;
vector<int> A(n), B(m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
int x;
cin >> x;
sum_matrix += x;
if(x == 1)
add_edge(i, j + n, 1, 0);
else
add_edge(i, j + n, 1, 1);
}
for(int i = 0; i < n; i++)
{
cin >> A[i];
add_edge(s, i, A[i], 0);
}
for(int i = 0; i < m; i++)
{
cin >> B[i];
add_edge(i + n, t, B[i], 0);
}
auto res = MCMF();
if(res.first != get_sum(A) || res.first != get_sum(B))
cout << -1 << endl;
else
cout << sum_matrix - res.first + res.second * 2 << endl;
}
Idea: Ferume, preparation: Ferume
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second
using namespace std;
struct sparse_table {
vector<vector<int>> st;
vector<int> pw;
sparse_table() {}
sparse_table(const vector<int> &a) {
int n = a.size();
int logn = 32 - __builtin_clz(n);
st.resize(logn, vector<int>(n));
forn(i, n)
st[0][i] = a[i];
for (int j = 1; j < logn; ++j) forn(i, n) {
st[j][i] = st[j - 1][i];
if (i + (1 << (j - 1)) < n)
st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]);
}
pw.resize(n + 1);
pw[0] = pw[1] = 0;
for (int i = 2; i <= n; ++i)
pw[i] = pw[i >> 1] + 1;
}
int get(int l, int r) {
if (l >= r) return 1e9;
int len = pw[r - l];
return min(st[len][l], st[len][r - (1 << len)]);
}
};
struct suffix_array {
vector<int> c, pos;
vector<pair<pair<int, int>, int>> p, nw;
vector<int> cnt;
int n;
void radix_sort(int max_al) {
cnt.assign(max_al, 0);
forn(i, n) ++cnt[p[i].x.y];
for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1];
nw.resize(n);
forn(i, n) nw[--cnt[p[i].x.y]] = p[i];
cnt.assign(max_al, 0);
forn(i, n) ++cnt[nw[i].x.x];
for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i) p[--cnt[nw[i].x.x]] = nw[i];
}
vector<int> lcp;
sparse_table st;
int get_lcp(int l, int r) {
l = c[l], r = c[r];
if (l > r) swap(l, r);
return st.get(l, r);
}
suffix_array(const string &s) {
n = s.size();
c = vector<int>(s.begin(), s.end());
int max_al = *max_element(c.begin(), c.end()) + 1;
p.resize(n);
for (int k = 1; k < n; k <<= 1) {
for (int i = 0, j = k; i < n; ++i, j = (j + 1 == n ? 0 : j + 1))
p[i] = make_pair(make_pair(c[i], c[j]), i);
radix_sort(max_al);
c[p[0].y] = 0;
for (int i = 1; i < n; ++i) c[p[i].y] = c[p[i - 1].y] + (p[i].x != p[i - 1].x);
max_al = c[p.back().y] + 1;
}
lcp.resize(n);
int l = 0;
forn(i, n) {
l = max(0, l - 1);
if (c[i] == n - 1)
continue;
while (i + l < n && p[c[i] + 1].y + l < n && s[i + l] == s[p[c[i] + 1].y + l])
++l;
lcp[c[i]] = l;
}
pos.resize(n);
forn(i, n)
pos[i] = p[i].y;
st = sparse_table(lcp);
}
};
int main() {
string s;
int n;
cin >> n;
cin >> s;
string t = s;
reverse(t.begin(), t.end());
auto sa = suffix_array(s + "#" + t + "$");
vector<vector<int>> ev0(n), ev1(n);
long long base = 0;
vector<long long> dt(n + 2);
vector<int> d1(n);
forn(i, n){
int len0 = sa.get_lcp(i, 2 * n - i + 1);
base += len0;
dt[i - len0] += 1;
dt[i] -= 1;
dt[i + 1] -= 1;
dt[i + len0 + 1] += 1;
if (i - len0 - 1 >= 0 && i + len0 < n){
ev0[i - len0 - 1].push_back(i);
ev0[i + len0].push_back(i);
}
int len1 = sa.get_lcp(i, 2 * n - i);
d1[i] = len1;
dt[i - len1 + 1] += 1;
dt[i + 1] -= 2;
dt[i + len1 + 1] += 1;
base += len1;
if (i - len1 >= 0 && i + len1 < n){
ev1[i - len1].push_back(i);
ev1[i + len1].push_back(i);
}
}
vector<long long> dx(n + 1);
long long curt = 0, val = 0;
forn(i, n){
curt += dt[i];
val += curt;
dx[i] = val;
}
long long ans = base;
int pos = -1, nc = -1;
bool gr = false;
forn(i, n) forn(c, 26) if (c != s[i] - 'a'){
long long cur = base;
for (int j : ev0[i]){
if (j <= i && c == s[2 * j - i - 1] - 'a')
cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 2));
else if (j > i && c == s[2 * j - i - 1] - 'a')
cur += 1 + sa.get_lcp(2 * j - i, 2 * n - (i - 1));
}
for (int j : ev1[i]){
if (c != s[2 * j - i] - 'a') continue;
if (j < i)
cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 1));
else
cur += 1 + sa.get_lcp(2 * j - i + 1, 2 * n - (i - 1));
}
cur += d1[i];
cur -= dx[i];
bool upd = false;
if (cur > ans){
upd = true;
}
else if (cur == ans){
if (c < s[i] - 'a'){
if (pos == -1 || gr)
upd = true;
}
else{
if (pos < i && gr)
upd = true;
}
}
if (upd){
ans = cur;
pos = i;
nc = c;
gr = c > s[i] - 'a';
}
}
cout << ans << endl;
if (pos != -1) s[pos] = nc + 'a';
cout << s << endl;
return 0;
}