First, I apologize for problems with round and serious problem with Div1A/Div2C. It was very important round for me and, as always, something goes wrong. KAN have already wrote about this.
Anyway, there are problems, so editorial must exists. Due some circumstances, Editorial will be upload in parts. Also, most of tutorials will contain main ideas how to solve task, not ready algorithm.
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;
}
