Idea: BledDest, preparation: awoo
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n, m, m2;
vector<vector<char>> g;
int T;
vector<int> mt;
vector<int> used;
bool try_kuhn(int v){
if (used[v] == T)
return false;
used[v] = T;
forn(u, m2) if (g[v][u] && (mt[u] == -1 || try_kuhn(mt[u]))){
mt[u] = v;
return true;
}
return false;
}
int main() {
cin >> n >> m;
vector<string> b(m, string(n, '0'));
forn(i, n){
string t;
cin >> t;
forn(j, m) b[j][i] = t[j];
}
vector<string> nw = b;
sort(nw.begin(), nw.end());
nw.resize(unique(nw.begin(), nw.end()) - nw.begin());
m2 = nw.size();
g.assign(m2, vector<char>(m2, 0));
forn(i, m2) forn(j, m2) if (i != j){
bool in = true;
forn(k, n) in &= nw[i][k] >= nw[j][k];
if (in) g[i][j] = 1;
}
mt.assign(m2, -1);
used.assign(m2, -1);
T = 0;
int k = m2;
forn(i, m2) if (try_kuhn(i)){
++T;
--k;
}
vector<int> nxt(m2, -1);
vector<char> st(m2, true);
forn(i, m2) if (mt[i] != -1){
nxt[mt[i]] = i;
st[i] = false;
}
vector<int> gr(m2), req(m2);
int t = 0;
forn(i, m2) if (st[i]){
int v = i;
int pos = 2;
while (v != -1){
gr[v] = t;
req[v] = pos;
++pos;
v = nxt[v];
}
++t;
}
assert(t == k);
vector<int> num(m);
forn(i, m) num[i] = lower_bound(nw.begin(), nw.end(), b[i]) - nw.begin();
printf("%d\n", k);
forn(i, m) printf("%d ", gr[num[i]] + 1);
puts("");
forn(i, m) printf("%d ", req[num[i]]);
puts("");
forn(i, n){
vector<int> l(k, 1);
forn(j, m2) if (nw[j][i] == '1')
l[gr[j]] = max(l[gr[j]], req[j]);
forn(j, k)
printf("%d ", l[j]);
puts("");
}
return 0;
}
Idea: vovuh, preparation: vovuh
Tutorial
Tutorial is loading...
Solution (vovuh)
for _ in range(int(input())):
n = int(input())
s = input()
print('YES' if n % 3 != 2 and not False in [s[i * 3 + 1] == s[i * 3 + 2] for i in range(n // 3)] else 'NO')
Idea: DStepanenko, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fore(i, l, r) for (int i = int(l); i < int(r); i++)
using namespace std;
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int binpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
vector<int> fact(4 * n + 1);
fact[0] = 1;
fore(i, 1, fact.size()) fact[i] = mul(fact[i - 1], i);
vector<int> rfact(4 * n + 1);
rfact.back() = binpow(fact.back(), MOD - 2);
for (int i = int(fact.size()) - 2; i >= 0; --i)
rfact[i] = mul(rfact[i + 1], i + 1);
auto cnk = [&](int n, int k){
return mul(fact[n], mul(rfact[k], rfact[n - k]));
};
vector<vector<int>> sv(n + 1, vector<int>(5));
forn(i, n + 1) forn(t, 5) sv[i][t] = mul(binpow(cnk(n, i), t), rfact[t]);
vector<vector<vector<int>>> dp(2, vector<vector<int>>(4 * n + 1, vector<int>(5)));
forn(ii, n + 1){
int i = ii & 1;
int ni = i ^ 1;
dp[ni] = vector<vector<int>>(4 * n + 1, vector<int>(5));
for (int t = 1; t <= 4; ++t)
dp[ni][ii * t][t] = mul(n - ii, sv[ii][t]);
forn(j, k + 1) for (int p = 1; p <= 4; ++p) if (dp[i][j][p]){
dp[ni][j][p] = add(dp[ni][j][p], dp[i][j][p]);
for (int t = 1; p + t <= 4; ++t)
dp[ni][j + ii * t][p + t] = add(dp[ni][j + ii * t][p + t], mul(dp[i][j][p], sv[ii][t]));
}
}
int ans = 0;
forn(sum, k + 1){
ans = add(ans, mul(mul(mul(
sum < k ? 1 : 4 * n - k,
dp[(n & 1) ^ 1][sum][4]),
mul(binpow(4 * n - sum, MOD - 2), mul(rfact[4 * n], fact[4 * n - sum]))),
mul(fact[4], fact[sum]))
);
}
printf("%d\n", ans);
return 0;
}
Idea: BledDest, preparation: DmitryKlenov
Tutorial
Tutorial is loading...
Solution (DmitryKlenov)
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200000
int a[N], n, s;
bool can(int x) {
int l = x - 1, r = n - 1;
while (l < r) {
if (a[r] > s - a[l]) return false;
++l;
if (l < r) {
if (a[l] > s - a[r]) return false;
--r;
}
}
return true;
}
int main() {
long long sum = 0;
scanf("%d %d\n", &n, &s);
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
sum += a[i];
}
sort(a, a + n, greater<int>());
int l = 1, r = n;
while (l < r) {
int m = (l + r) >> 1;
if (can(m)) r = m;
else l = m + 1;
}
long long ans = sum + r;
cout << ans << endl;
return 0;
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, a, b;
cin >> n >> a >> b;
int x = (n + a - 1) / a;
if(a > b) x = 1;
cout << x << endl;
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
typedef long long li;
const li INF64 = 1e18;
struct base{
int x, w, c;
};
li area(const base &a, const base &b){
return (a.c + b.c) * li(abs(a.x - b.x));
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
vector<base> a(n);
forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].w, &a[i].c);
sort(a.begin(), a.end(), [](const base &a, const base &b){ return a.x > b.x; });
vector<li> dp(n, -INF64);
li ans = 0;
forn(i, n){
dp[i] = max(dp[i], -a[i].w * 200ll);
for (int j = i + 1; j < n; ++j)
dp[j] = max(dp[j], dp[i] + area(a[i], a[j]) * k - a[j].w * 200ll);
ans = max(ans, dp[i]);
}
printf("%.15Lf\n", ans / (long double)(200));
return 0;
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(42);
uniform_int_distribution<int> d(1, 2);
int ask(int t, int i)
{
cout << t << " " << i + 1 << endl;
int x;
cin >> x;
return x;
}
void giveAnswer(const string& s)
{
cout << 0 << " " << s << endl;
int x;
cin >> x;
assert(x == 1);
}
void guessOne(string& s, int i)
{
int res = ask(1, i);
if(res == 0)
s[i] = '1';
else
s[i] = s[res - 1];
}
char inv(char c)
{
if(c == '0') return '1';
return '0';
}
void guessTwo(string& s, int i)
{
if(s[1] == '0')
{
if(d(rnd) == 1)
{
int res = ask(1, i);
if(res >= 2)
{
s[i] = s[res - 1];
s[i - 1] = s[res - 2];
}
else if(res == 1)
{
s[i] = '0';
s[i - 1] = '1';
}
else
{
s[i] = '1';
guessOne(s, i - 1);
}
}
else
{
int res = ask(2, i);
if(res >= 2)
{
s[i] = inv(s[res - 1]);
s[i - 1] = inv(s[res - 2]);
}
else if(res == 1)
{
s[i] = '1';
s[i - 1] = '0';
}
else
{
s[i] = '0';
guessOne(s, i - 1);
}
}
}
else
{
if(d(rnd) == 1)
{
int res = ask(1, i);
if(res >= 2)
{
s[i] = s[res - 1];
s[i - 1] = s[res - 2];
}
else if(res == 1)
{
s[i] = '0';
guessOne(s, i - 1);
}
else
{
s[i] = '1';
s[i - 1] = '1';
}
}
else
{
int res = ask(2, i);
if(res >= 2)
{
s[i] = inv(s[res - 1]);
s[i - 1] = inv(s[res - 2]);
}
else if(res == 1)
{
s[i] = '1';
guessOne(s, i - 1);
}
else
{
s[i] = '0';
s[i - 1] = '0';
}
}
}
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
string s(n, '0');
for(int j = 1; j < n; j += 2)
{
if(j == 1) guessOne(s, j);
else guessTwo(s, j);
}
if(n % 2 == 1) guessOne(s, n - 1);
giveAnswer(s);
}
}
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &x : a) cin >> x;
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
g[y - 1].push_back(x - 1);
}
vector<int> ans(n, -1);
for (int s = 0; s < n; ++s) {
vector<int> deg(n);
for (int i = 0; i < n; ++i)
for (int j : g[i]) ++deg[j];
priority_queue<pair<int, int>> q;
for (int v = 0; v < n; ++v)
if (deg[v] == 0 && v != s)
q.push({a[v], v});
for (int i = n; i > 0; --i) {
if (q.empty() || q.top().first < i) {
if (deg[s] == 0 && i <= a[s])
ans[s] = i;
break;
}
int v = q.top().second;
q.pop();
for (int u : g[v]) {
--deg[u];
if (deg[u] == 0 && u != s)
q.push({a[u], u});
}
}
}
for (int &x : ans) cout << x << ' ';
}
Idea: DmitryKlenov, preparation: dmitryme
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const string al = "KQRBN";
const int INF = 1e9;
struct mv{ int dx, dy; };
struct piece{ int x, y, t; };
struct seg{ int l, r; };
struct pos{ int x, y; };
bool operator <(const pos &a, const pos &b){
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
vector<vector<mv>> mvs({
{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}},
{{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
{{-1, 0}, {0, 1}, {1, 0}, {0, -1}},
{{-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
{{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}}
});
int main() {
int sx, sy, fx, fy;
cin >> sx >> sy >> fx >> fy;
swap(sx, sy), swap(fx, fy);
--sx, --fx;
int k;
cin >> k;
vector<piece> a(k);
forn(i, k){
string t;
cin >> t >> a[i].x >> a[i].y;
swap(a[i].x, a[i].y);
--a[i].x;
a[i].t = al.find(t[0]);
}
sort(a.begin(), a.end(), [](const piece &a, const piece &b){
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
});
vector<int> base({sy, fy});
forn(i, k) base.push_back(a[i].y);
vector<int> ys;
for (int y : base) for (int i = y - 16; i <= y + 16; ++i)
ys.push_back(i);
sort(ys.begin(), ys.end());
ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
vector<vector<char>> tk(8, vector<char>(ys.size()));
forn(i, k){
a[i].y = lower_bound(ys.begin(), ys.end(), a[i].y) - ys.begin();
tk[a[i].x][a[i].y] = true;
}
sy = lower_bound(ys.begin(), ys.end(), sy) - ys.begin();
fy = lower_bound(ys.begin(), ys.end(), fy) - ys.begin();
vector<vector<char>> bad = tk;
forn(i, k){
int x = a[i].x, y = a[i].y;
if (a[i].t == 0 || a[i].t == 4){
for (auto it : mvs[a[i].t]){
int nx = x + it.dx;
int ny = y + it.dy;
if (0 <= nx && nx < 8)
bad[nx][ny] = true;
}
}
else{
for (auto it : mvs[a[i].t]){
for (int nx = x + it.dx, ny = y + it.dy; ; nx += it.dx, ny += it.dy){
if (nx < 0 || nx >= 8) break;
if (ny < 0 || ny >= int(ys.size())) break;
if (tk[nx][ny]) break;
bad[nx][ny] = true;
}
}
}
}
vector<vector<int>> d(8, vector<int>(ys.size(), INF));
vector<vector<pos>> p(8, vector<pos>(ys.size()));
set<pair<int, pos>> q;
d[sx][sy] = 0;
q.insert({0, {sx, sy}});
while (!q.empty()){
int x = q.begin()->second.x;
int y = q.begin()->second.y;
q.erase(q.begin());
if (x == fx && y == fy){
cout << d[x][y] << endl;
return 0;
}
for (int ny : {y - 1, y, y + 1}){
if (ny < 0 || ny >= int(ys.size())) continue;
int dy = max(1, abs(ys[y] - ys[ny]));
for (int nx = max(0, x - 1); nx <= min(7, x + 1); ++nx) if (!bad[nx][ny]){
int nd = d[x][y] + dy;
if (d[nx][ny] > nd){
q.erase({d[nx][ny], {nx, ny}});
d[nx][ny] = nd;
p[nx][ny] = {x, y};
q.insert({d[nx][ny], {nx, ny}});
}
}
}
}
cout << -1 << endl;
return 0;
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
vector<int> a(n), b(n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < n; i++) scanf("%d", &b[i]);
sort(a.begin(), a.end());
sort(b.begin(), b.end());
long long total = 0;
for(int i = 0; i < n; i++)
{
total += n * 1ll * (a[i] + b[i]);
total -= a[i] * 2ll * (b.end() - lower_bound(b.begin(), b.end(), a[i]));
total -= b[i] * 2ll * (a.end() - upper_bound(a.begin(), a.end(), b[i]));
}
for(int i = 0; i < n; i++)
total -= (n - 1) * 1ll * abs(a[i] - b[i]);
cout << total << endl;
}
Idea: adedalic, preparation: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
int n;
vector< vector<int> > a;
bool read() {
if (!(cin >> n))
return false;
a.resize(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cin >> a[i][j];
}
return true;
}
void solve() {
long long sum = 0;
for (int i = 0; i < n; i++)
sum += accumulate(a[i].begin(), a[i].end(), 0LL);
int mn = a[0][n - 1];
for (int i = 0; i < n; i++)
mn = min(mn, a[i][n - 1 - i]);
cout << sum - mn << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: BledDest, preparation: awoo
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const string days[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
int main() {
cin.tie(0);
iostream::sync_with_stdio(false);
int n, m, k;
cin >> n >> m >> k;
vector<vector<char>> ds(n, vector<char>(7));
forn(i, n){
int t;
cin >> t;
forn(_, t){
string s;
cin >> s;
ds[i][find(days, days + 7, s) - days] = true;
}
}
vector<int> h(m);
forn(i, m) cin >> h[i];
vector<vector<int>> a(k);
forn(i, k){
int p;
cin >> p;
a[i].resize(p);
forn(j, p){
cin >> a[i][j];
--a[i][j];
}
}
int j = 0;
vector<int> ans(k, -1), lst(k);
int done = 0;
vector<map<int, int>> cur(7);
vector<set<int>> wk(n);
forn(i, k) forn(j, 7) if (ds[a[i][0]][j])
++cur[j][a[i][0]];
forn(i, k)
wk[a[i][0]].insert(i);
for (int d = 1;; ++d){
if (j < m && h[j] == d){
++j;
continue;
}
int wd = (d - 1) % 7;
vector<int> now, sv;
for (auto it : cur[wd]) now.push_back(it.first);
for (int x : now){
forn(i, 7){
auto it = cur[i].find(x);
if (it != cur[i].end()){
if (it->second == 1)
cur[i].erase(it);
else
--it->second;
}
}
int y = *wk[x].begin();
sv.push_back(y);
wk[x].erase(wk[x].begin());
}
forn(i, now.size()){
int y = sv[i];
++lst[y];
if (lst[y] == int(a[y].size())){
ans[y] = d;
++done;
continue;
}
wk[a[y][lst[y]]].insert(y);
forn(j, 7) if (ds[a[y][lst[y]]][j])
++cur[j][a[y][lst[y]]];
}
if (done == k) break;
}
forn(i, k) cout << ans[i] << " ";
cout << endl;
}
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a = 1;
for (int g = 2; g * g <= n; ++g) {
if (n % g == 0) {
a = n / g;
break;
}
}
cout << a << ' ' << n - a << '\n';
}
}
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
string x;
cin >> x;
int k;
cin >> k;
int n = x.size();
vector<vector<int>> pos(10);
for (int i = 0; i < n; ++i)
pos[x[i] - '0'].push_back(i);
for (int i = 0; i < 10; ++i)
reverse(pos[i].begin(), pos[i].end());
string ans;
int lst = 0, len = n - k;
for (int i = 0; i < len; ++i) {
for (int d = (i == 0); d <= 9; ++d) {
while (!pos[d].empty() && pos[d].back() < lst)
pos[d].pop_back();
if (!pos[d].empty() && pos[d].back() - lst <= k) {
ans += d + '0';
k -= pos[d].back() - lst;
lst = pos[d].back() + 1;
break;
}
}
}
cout << ans << '\n';
}
}