Codeforces Round #421 Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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