Codeforces Round #421 Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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

#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() &mdash; t << endl;
		t = gett();
#endif
	}
	return 0;
}

Tutorial is loading...

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 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 &mdash; 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() &mdash; t << endl;
		t = gett();
#endif
	}
	return 0;
}

Tutorial is loading...

code

Tutorial is loading...

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;

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() &mdash; t << endl;
		t = gett();
#endif
	}
	return 0;
}

Tutorial is loading...

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;
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() &mdash; t << endl;
		t = gett();
#endif
	return 0;
}

Tutorial is loading...

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 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 &mdash; 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 &mdash; 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() &mdash; t << endl;
		t = gett();
#endif
	}
	return 0;
}

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;
}

Rev.	By	When	Δ	Comment
ru1	adedalic	2017-06-28 17:40:28	9572	Первая редакция перевода на Русский
en11	adedalic	2017-06-28 17:35:28	5513	Tiny change: 'rn (a + b — 1) / b;\n' -> 'rn (a + b - 1) / b;\n'
en10	adedalic	2017-06-28 01:50:03	0	(published)
en9	adedalic	2017-06-28 01:46:24	2012
en8	adedalic	2017-06-28 01:43:41	56
en7	adedalic	2017-06-28 01:42:04	24
en6	adedalic	2017-06-28 01:40:14	10
en5	adedalic	2017-06-28 01:39:13	9077
en4	adedalic	2017-06-28 01:36:10	331
en3	adedalic	2017-06-28 01:34:44	1758
en2	adedalic	2017-06-28 01:16:21	9
en1	adedalic	2017-06-28 01:15:57	2156	Initial revision (saved to drafts)

History