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. [user:KAN,2017-06-28] have already [wrote about this](http://mirror.codeforces.com/blog/entry/52944).↵
↵
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:820A]↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#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↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵
↵
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;↵
}↵
↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
while(read()) {↵
solve(); ↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() — t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:820B]↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#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↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵
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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:820B]↵
↵
<spoiler summary="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;↵
}↵
↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
while(read()) {↵
solve(); ↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() — t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:819A]↵
↵
<spoiler summary="code">↵
</spoiler>↵
↵
[tutorial:819B]↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#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↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795typedef 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;↵
}↵
↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
while(read()) {↵
solve(); ↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() — t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:819C]↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#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↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
typedef pair<li, li> ptl;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;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;↵
const ld PI = 3.1415926535897932384626433832795;↵
↵
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);↵
}↵
↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
int tc; assert(cin >> tc);↵
precalc();↵
↵
while(tc--) {↵
assert(read());↵
↵
solve(); ↵
}↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() — t << endl;↵
t = gett();↵
#endif↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:819D]↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#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↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << ", ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵
↵
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("");↵
}↵
↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
while(read()) {↵
solve(); ↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() — t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:819E]↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
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:820A]↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
#define forn(i, n) fore(i, 0, n)↵
↵
#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↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵
↵
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;↵
}↵
↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
while(read()) {↵
solve(); ↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() — t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:820B]↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#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↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵
↵
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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:820B]↵
↵
<spoiler summary="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
↵
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;↵
}↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
while(read()) {↵
solve(); ↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() — t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
</spoiler>↵
↵
[tutorial:819A]↵
↵
<spoiler summary="code">↵
</spoiler>↵
↵
[tutorial:819B]↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
#define forn(i, n) fore(i, 0, n)↵
↵
#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↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795
↵
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;↵
}↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
while(read()) {↵
solve(); ↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() — t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
</spoiler>↵
↵
[tutorial:819C]↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
#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 y second↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
typedef pair<li, li> ptl;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;
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);↵
}↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
int tc; assert(cin >> tc);↵
precalc();↵
↵
while(tc--) {↵
assert(read());↵
↵
solve(); ↵
}↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() — t << endl;↵
t = gett();↵
#endif↵
return 0;↵
}↵
</spoiler>↵
↵
[tutorial:819D]↵
↵
<spoiler summary="code">↵
~~~~~↵
↵
#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↵
↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << ", ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;
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
}↵
↵
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
↵
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("");↵
}↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
while(read()) {↵
solve(); ↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() — t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
</spoiler>↵
↵
[tutorial:819E]↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
