Для начала, извиняюсь за проблемы с раундом и задачей Div1A/Div2C в частности. Это был очень важный раунд для меня и, как это иногда бывает, что-то пошло не так. KAN уже написал по данному поводу.
В любом случае, есть задачи, а значит нужны решения. Разбор на русском запоздал, но все же. Также, большинство разборов будут концентрироваться на ключевых идеях решения.
Tutorial is loading...
code
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)
int c, l, v0, v1, a;
inline bool read() {
if(!(cin >> c >> v0 >> v1 >> a >> l))
return false;
return true;
}
inline void solve() {
int pos = v0;
int t = 1;
int add = v0;
while(pos < c) {
add = min(v1, add + a);
pos += add - l;
t++;
}
cout << t << endl;
}
Tutorial is loading...
code
int n, a;
inline bool read() {
if(!(cin >> n >> a))
return false;
return true;
}
inline void solve() {
int base = n * a / 180;
base = max(1, min(n - 2, base));
int bk = base;
for(int ck = max(1, base - 2); ck <= min(n - 2, base + 2); ck++) {
if(abs(180 * ck - n * a) < abs(180 * bk - n * a))
bk = ck;
}
cout << 2 << " " << 1 << " " << bk + 2 << endl;
}
Tutorial is loading...
code
Tutorial is loading...
code
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)
typedef long long li;
const int N = 1000 * 1000 + 555;
int n, p[N];
inline bool read() {
if(!(cin >> n))
return false;
forn(i, n)
assert(scanf("%d", &p[i]) == 1);
return true;
}
li sum[N], df[N], res[N];
inline void add(int lf, int rg, int k, int b) {
if(lf > rg)
return;
sum[lf] += b;
df[lf] += k;
sum[rg + 1] -= b + k * 1ll * (rg - lf);
df[rg] -= k;
}
inline void calc() {
li curdf = 0;
forn(i, n) {
sum[i] += curdf;
curdf += df[i];
}
li cursm = 0;
forn(i, n) {
cursm += sum[i];
res[i] += cursm;
}
}
inline void solve() {
memset(sum, 0, sizeof sum);
memset(df, 0, sizeof df);
memset(res, 0, sizeof res);
forn(i, n) {
int c1 = i + 1, p1 = 0;
int c2 = n, p2 = p1 + c2 - c1;
int c3 = i, p3 = p2 + c3;
if(p[i] <= c3) {
add(p1, p2, 1, c1 - p[i]);
add(p2 + 1, p2 + p[i], -1, p[i] - 1);
add(p2 + p[i] + 1, p3, 1, 1);
} else {
add(p1, p1 + p[i] - c1, -1, p[i] - c1);
add(p1 + p[i] - c1 + 1, p2, 1, 1);
add(p2 + 1, p3, -1, p[i] - 1);
}
}
calc();
int ans = 0;
forn(i, n)
if(res[ans] > res[i])
ans = i;
cout << res[ans] << " " << ans << endl;
}
Tutorial is loading...
code
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)
#define all(a) (a).begin(), (a).end()
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back
typedef long long li;
typedef pair<int, int> pt;
typedef pair<li, li> ptl;
const int INF = int(1e9);
const li INF64 = li(INF) * INF;
int n[3], m[3], s[3];
inline bool read() {
if(scanf("%d %d %d", &n[0], &n[1], &n[2]) != 3)
return false;
forn(i, 3)
assert(scanf("%d", &m[i]) == 1);
forn(i, 3)
assert(scanf("%d", &s[i]) == 1);
return true;
}
const int N = 2 * 1000 * 1000 + 55;
int ls[N];
inline void precalc() {
memset(ls, -1, sizeof ls);
ls[0] = ls[1] = 1;
fore(i, 2, N) {
if(ls[i] != -1)
continue;
ls[i] = i;
for(li j = i * 1ll * i; j < N; j += i)
if(ls[j] == -1)
ls[j] = i;
}
}
inline vector<pt> fact(int n[3]) {
vector<int> divs;
forn(i, 3) {
int cur = n[i];
while(ls[cur] != cur) {
divs.pb(ls[cur]);
cur /= ls[cur];
}
if(cur > 1)
divs.pb(cur);
}
sort(all(divs));
vector<pt> ans;
int u = 0;
while(u < sz(divs)) {
int v = u;
while(v < sz(divs) && divs[v] == divs[u])
v++;
ans.pb(mp(divs[u], v - u));
u = v;
}
return ans;
}
li ans;
li nn, mm, ss;
vector<pt> fs;
vector<li> bad;
void calcDivs(int pos, li val) {
if(pos >= sz(fs)) {
ans += (val <= nn);
return;
}
li cv = 1;
forn(i, fs[pos].y + 1) {
calcDivs(pos + 1, val * cv);
cv *= fs[pos].x;
}
}
void calcInEx(int pos, li val, int cnt) {
if(pos >= sz(bad)) {
li k = cnt ? -1 : 1;
ans += k * (mm / val);
return;
}
calcInEx(pos + 1, val, cnt);
calcInEx(pos + 1, val * bad[pos], cnt ^ 1);
}
inline void solve() {
ans = 0;
s[0] *= 2;
nn = n[0] * 1ll * n[1] * 1ll * n[2];
mm = m[0] * 1ll * m[1] * 1ll * m[2];
ss = s[0] * 1ll * s[1] * 1ll * s[2];
fs = fact(s);
calcDivs(0, 1);
bad.clear();
vector<pt> fn = fact(n);
forn(i, sz(fn)) {
li cv = fn[i].x;
forn(k, fn[i].y) {
if(ss % cv != 0) {
bad.pb(cv);
break;
}
cv *= fn[i].x;
}
}
calcInEx(0, 1, 0);
printf("%I64d\n", ans);
}
Tutorial is loading...
code
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)
#define all(a) (a).begin(), (a).end()
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(INF) * INF;
int gcd(int a, int b) {
if(a == 0)
return b;
return gcd(b % a, a);
}
int exgcd(int a, li &x, int b, li &y) {
if(a == 0) {
x = 0, y = 1;
return b;
}
li xx, yy;
int g = exgcd(b % a, xx, a, yy);
x = yy - b / a * xx;
y = xx;
return g;
}
const int N = 200 * 1000 + 555;
int t, n, a[N];
inline bool read() {
if(!(cin >> t >> n))
return false;
forn(i, n)
assert(scanf("%d", &a[i]) == 1);
return true;
}
int pf[N], s;
inline li up(li a, li b) {
return (a + b - 1) / b;
}
inline int findPos(int a, int b, int c) {
li x, y;
int g = exgcd(a, x, b, y);
assert(c % g == 0);
x *= +c / g;
y *= -c / g;
assert(a * 1ll * x - b * 1ll * y == c);
int ag = a / g;
int bg = b / g;
li k = 0;
if(x < 0)
k = up(-x, bg);
if(x >= bg)
k = -up(x - bg, bg);
x += bg * k;
y += ag * k;
assert(0 <= x && x < bg);
k = 0;
if(y < 0)
k = up(-y, ag);
x += bg * k;
y += ag * k;
return x;
}
map< int, set<pt> > cycle;
int ans[N];
inline void solve() {
cycle.clear();
pf[0] = 0;
fore(i, 1, n)
pf[i] = (pf[i - 1] + a[i]) % t;
s = (a[0] + pf[n - 1]) % t;
int g = gcd(s, t);
forn(i, n) {
int st = pf[i] % g;
auto& cc = cycle[st];
int pos = findPos(s, t, pf[i] - st);
if(cc.empty()) {
ans[i] += t / g;
cc.insert(pt(pos, -i));
} else {
auto rg = cc.lower_bound(pt(pos, -i));
if(rg == cc.end()) {
ans[i] += t / g - pos;
rg = cc.begin();
ans[i] += rg->x;
} else
ans[i] += rg->x - pos;
auto lf = cc.lower_bound(pt(pos, -i));
if(lf == cc.begin())
lf = --cc.end();
else
lf--;
ans[ -(lf->y) ] -= ans[i];
cc.insert(pt(pos, -i));
}
}
forn(i, n)
printf("%d ", ans[i]);
puts("");
}
Tutorial is loading...
code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
#ifdef WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
const int maxn = 305;
int pair3[maxn];
int n;
vector<vector<int>> answer;
void add3(int a, int b, int c)
{
answer.pb({a, b, c});
}
void add4(int a, int b, int c, int d)
{
answer.pb({a, b, c, d});
}
int main()
{
cin >> n;
if (n % 2 == 0)
{
pair3[0] = 3; // 0 1 3
pair3[2] = 1; // 2 3 1
add3(0, 1, 2);
add3(2, 3, 0);
for (int i = 4; i < n; i += 2)
{
add4(0, pair3[0], 1, i);
add3(i, i + 1, 0);
pair3[i] = 1;
pair3[0] = i + 1;
for (int j = 2; j < i; j += 2)
{
add4(j, pair3[j], j + 1, i);
add4(j, i, j + 1, i + 1);
pair3[j] = i + 1;
}
}
for (int i = 0; i < n; i += 2)
{
add3(i, i + 1, pair3[i]);
}
} else
{
pair3[1] = 0; // 1 2 0
add3(0, 1, 2);
for (int i = 3; i < n; i += 2)
{
add3(i, i + 1, 0);
pair3[i] = 0;
for (int j = 1; j < i; j += 2)
{
add4(j, pair3[j], j + 1, i);
add4(j, i, j + 1, i + 1);
pair3[j] = i + 1;
}
}
for (int i = 1; i < n; i += 2)
{
add3(i, i + 1, pair3[i]);
}
}
printf("%d\n", (int)answer.size());
for (auto &t : answer)
{
printf("%d", (int)t.size());
for (auto t2 : t) printf(" %d", t2 + 1);
printf("\n");
}
return 0;
}