1030A - In Search of an Easy Problem
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
int curMax = 0;
for(int i = 0; i < n; i++) {
int curAns; cin >> curAns;
curMax = max(curMax, curAns);
}
puts(curMax > 0 ? "HARD" : "EASY");
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int n, d;
int m;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> d;
cin >> m;
for(int i = 0; i < m; ++i){
int x, y;
cin >> x >> y;
bool ok = true;
if(!((x - y) <= d && (x - y) >= -d))
ok = false;
if(!((x + y) <= n + n - d && (x + y) >= d))
ok = false;
if(ok) puts("YES");
else puts("NO");
}
return 0;
}
1030C - Vasya and Golden Ticket
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> s;
int sum = 0;
for(int i = 0; i < n - 1; ++i){
sum += s[i] - '0';
bool ok = true;
int pos = i + 1;
int sum2 = 0;
while(pos < n){
sum2 = s[pos++] - '0';
while(pos < n && sum2 + s[pos] - '0' <= sum){
sum2 += s[pos] - '0';
++pos;
}
if(sum2 != sum) ok = false;
}
if(sum2 != sum) ok = false;
if(ok){
puts("YES");
return 0;
}
}
puts("NO");
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b){
return a? gcd(b % a, a) : b;
}
int main() {
//freopen("input.txt", "r", stdin);
long long n, m, k;
cin >> n >> m >> k;
bool isEven = k % 2 == 0;
long long p = n * m;
if(isEven) k /= 2;
if(p % k != 0){
cout << "NO" << endl;
return 0;
}
long long x = gcd(n, k);
k /= x;
long long a = n / x;
x = gcd(m, k);
k /= x;
assert(k == 1);
long long b = m / x;
if(!isEven){
if(a < n)
a += a;
else{
assert(b < m);
b += b;
}
}
cout << "YES" << endl;
cout << "0 0\n";
cout << 0 << ' ' << b << endl;
cout << a << ' ' << 0 << endl;
return 0;
}
1030E - Vasya and Good Sequences
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 9;
int n;
long long a[N];
int b[N];
int cnt[2][N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i <n; ++i){
cin >> a[i];
b[i] = __builtin_popcountll(a[i]);
}
long long res = 0;
int sufSum = 0;
cnt[0][n] = 1;
for(int i = n - 1; i >= 0; --i){
int sum = 0, mx = 0;
int lstJ = i;
int add = 0;
for(int j = i; j < n && j - i < 65; ++j){
sum += b[j];
mx = max(mx, b[j]);
if(mx > sum - mx && sum % 2 == 0) --add;
lstJ = j;
}
sufSum += b[i];
add += cnt[sufSum & 1][i + 1];
res += add;
cnt[0][i] = cnt[0][i + 1];
cnt[1][i] = cnt[1][i + 1];
if(sufSum & 1) ++cnt[1][i];
else ++cnt[0][i];
}
cout << res << endl;
return 0;
}
1030F - Putting Boxes Together
Tutorial
Tutorial is loading...
Fenwick Solution
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
typedef long long li;
const int MOD = int(1e9) + 7;
int norm(int a) {
if(a >= MOD)
a -= MOD;
if(a < 0)
a += MOD;
return a;
}
int norm(const li &a) {
return norm(int(a % MOD));
}
int mul(int a, int b) {
return int((a * 1ll * b) % MOD);
}
const int N = 200 * 1000 + 555;
int n, q;
int a[N], w[N];
inline bool read() {
if(!(cin >> n >> q))
return false;
fore(i, 0, n)
assert(scanf("%d", &a[i]) == 1);
fore(i, 0, n)
assert(scanf("%d", &w[i]) == 1);
return true;
}
li fW[N], fAW[N];
void inc(li f[N], int pos, li val) {
for(; pos < N; pos |= pos + 1)
f[pos] += val;
}
li sum(li f[N], int pos) {
li ans = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
ans += f[pos];
return ans;
}
li getSum(li f[N], int l, int r) {
return sum(f, r - 1) - sum(f, l - 1);
}
int getNSum(li f[N], int l, int r) {
return norm(sum(f, r - 1) - sum(f, l - 1));
}
inline void solve() {
fore(i, 0, n) {
a[i] -= i;
inc(fW, i, w[i]);
inc(fAW, i, mul(a[i], w[i]));
}
fore(_, 0, q) {
int x, y;
assert(scanf("%d%d", &x, &y) == 2);
if(x < 0) {
x = -x - 1;
inc(fW, x, -w[x]);
inc(fAW, x, -mul(a[x], w[x]));
w[x] = y;
inc(fW, x, w[x]);
inc(fAW, x, mul(a[x], w[x]));
} else {
x--;
li sum = getSum(fW, x, y);
int lf = x, rg = y;
while(rg - lf > 1) {
int mid = (lf + rg) >> 1;
if(2 * getSum(fW, x, mid) > sum)
rg = mid;
else
lf = mid;
}
assert(x <= lf && lf < y);
int ans = norm(mul(a[lf], getNSum(fW, x, lf)) - getNSum(fAW, x, lf));
ans = norm(ans + norm(getNSum(fAW, lf, y) - mul(a[lf], getNSum(fW, lf, y))) );
printf("%d\n", ans);
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Segment Tree Solution
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
out << "[";
fore(i, 1, int(v.size())) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = int(1e9) + 7;
int norm(int a) {
while(a >= MOD)
a -= MOD;
while(a < 0)
a += MOD;
return a;
}
int norm(const li &a) {
return norm(int(a % MOD));
}
int mul(int a, int b) {
return int((a * 1ll * b) % MOD);
}
const int N = 300 * 1000 + 555;
int n, q;
int a[N], w[N];
inline bool read() {
if(!(cin >> n >> q))
return false;
fore(i, 0, n)
assert(scanf("%d", &a[i]) == 1);
fore(i, 0, n)
assert(scanf("%d", &w[i]) == 1);
return true;
}
li TW[4 * N], TAW[4 * N];
void addVAl(li T[4 * N], int v, int l, int r, int pos, int val) {
if(l + 1 == r) {
assert(l == pos);
T[v] += val;
return;
}
int mid = (l + r) >> 1;
if(pos < mid)
addVAl(T, 2 * v + 1, l, mid, pos, val);
else
addVAl(T, 2 * v + 2, mid, r, pos, val);
T[v] = T[2 * v + 1] + T[2 * v + 2];
}
li getSum(li T[4 * N], int v, int l, int r, int lf, int rg) {
if(l == lf && r == rg)
return T[v];
int mid = (l + r) >> 1;
li ans = 0;
if(lf < mid)
ans += getSum(T, 2 * v + 1, l, mid, lf, min(mid, rg));
if(rg > mid)
ans += getSum(T, 2 * v + 2, mid, r, max(lf, mid), rg);
return ans;
}
int getNSum(li T[4 * N], int l, int r) {
if(l >= r) return 0;
return int(getSum(T, 0, 0, n, l, r) % MOD);
}
pair<int, li> getPos(int v, int l, int r, int lf, int rg, li val) {
if(l == lf && r == rg) {
if(TW[v] <= val)
return make_pair(INF, TW[v]);
if(l + 1 == r)
return make_pair(l, 0);
}
int mid = (l + r) >> 1;
int res = INF;
li sum = 0;
if(lf < mid) {
auto cur = getPos(2 * v + 1, l, mid, lf, min(mid, rg), val);
res = min(res, cur.x);
sum += cur.y;
}
if(rg > mid && res == INF) {
auto cur = getPos(2 * v + 2, mid, r, max(lf, mid), rg, val - sum);
res = min(res, cur.x);
sum += cur.y;
}
return make_pair(res, sum);
}
inline void solve() {
fore(i, 0, n) {
a[i] -= i;
addVAl(TW, 0, 0, n, i, w[i]);
addVAl(TAW, 0, 0, n, i, mul(a[i], w[i]));
}
fore(_, 0, q) {
int x, y;
assert(scanf("%d%d", &x, &y) == 2);
if(x < 0) {
x = -x - 1;
addVAl(TW, 0, 0, n, x, -w[x]);
addVAl(TAW, 0, 0, n, x, -mul(a[x], w[x]));
w[x] = y;
addVAl(TW, 0, 0, n, x, w[x]);
addVAl(TAW, 0, 0, n, x, mul(a[x], w[x]));
} else {
x--;
li sum = getSum(TW, 0, 0, n, x, y);
int pos = getPos(0, 0, n, x, y, sum / 2).x;
assert(x <= pos && pos < y);
int ans = norm(mul(a[pos], getNSum(TW, x, pos)) - getNSum(TAW, x, pos));
ans = norm(ans + norm(getNSum(TAW, pos, y) - mul(a[pos], getNSum(TW, pos, y))) );
printf("%d\n", ans);
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
1030G - Linear Congruential Generator
Tutorial
Tutorial is loading...
Dynamic Connectivity Solution
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
out << "[";
fore(i, 0, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int MOD = int(1e9) + 7;
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
int ans = 1;
while(k > 0) {
if(k & 1) ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
const int M = 2000 * 1000 + 555;
const int N = 200 * 1000 + 555;
int n, p[N];
inline bool read() {
if(!(cin >> n))
return false;
fore(i, 0, n)
assert(scanf("%d", &p[i]) == 1);
return true;
}
int minD[M];
vector<pt> ps[M];
void precalc() {
iota(minD, minD + M, 0);
fore(i, 2, M) {
if(minD[i] < i)
continue;
for(li j = i * 1ll * i; j < M; j += i)
minD[j] = min(minD[j], i);
}
fore(i, 2, M) {
int v = i;
ps[i].clear();
while(v > 1) {
int md = minD[v];
if(ps[i].empty() || ps[i].back().x != md)
ps[i].emplace_back(md, 0);
ps[i].back().y++;
v /= md;
}
}
}
int baseA[M], cntNotZero = 0;
int a[M];
int mark[M];
void insert(int v) {
if(a[v] < 1) {
a[v] = 1;
mark[v] = 1;
return;
}
for(auto p : ps[v - 1]) {
a[p.x] = max(a[p.x], p.y);
if(mark[p.x]) {
mark[p.x] = 0;
insert(p.x);
}
}
}
vector<int*> pnt;
vector<int> val;
void upd(int &pos, int nval) {
pnt.push_back(&pos);
val.push_back(pos);
pos = nval;
}
void roll_back() {
*(pnt.back()) = val.back();
pnt.pop_back();
val.pop_back();
}
bool ok[N];
int cntSame = 0;
vector<int> Top[4 * N];
void addOp(int v, int l, int r, int lf, int rg, int val) {
if(l == lf && r == rg) {
Top[v].push_back(val);
return;
}
int mid = (l + r) >> 1;
if(lf < mid)
addOp(2 * v + 1, l, mid, lf, min(mid, rg), val);
if(rg > mid)
addOp(2 * v + 2, mid, r, max(lf, mid), rg, val);
}
void insertDC(int v) {
if(a[v] < 1) {
upd(a[v], 1);
upd(mark[v], 1);
if(a[v] == baseA[v])
upd(cntSame, cntSame + 1);
return;
}
for(auto p : ps[v - 1]) {
if(a[p.x] < p.y) {
upd(a[p.x], p.y);
if(a[p.x] == baseA[p.x])
upd(cntSame, cntSame + 1);
}
if(mark[p.x]) {
upd(mark[p.x], 0);
insertDC(p.x);
}
}
}
void calcAns(int v, int l, int r) {
int curOp = sz(pnt);
for(int cv : Top[v])
insertDC(cv);
if(l + 1 == r) {
ok[l] = cntSame == cntNotZero;
} else {
int mid = (l + r) >> 1;
calcAns(2 * v + 1, l, mid);
calcAns(2 * v + 2, mid, r);
}
while(sz(pnt) > curOp)
roll_back();
}
inline void solve() {
memset(baseA, 0, sizeof baseA);
memset(a, 0, sizeof a);
memset(mark, 0, sizeof mark);
fore(i, 0, n)
insert(p[i]);
cntNotZero = 0;
fore(i, 0, M) {
baseA[i] = a[i];
cntNotZero += a[i] > 0;
}
memset(a, 0, sizeof a);
memset(mark, 0, sizeof mark);
fore(i, 0, n) {
if(i > 0)
addOp(0, 0, n, 0, i, p[i]);
if(i + 1 < n)
addOp(0, 0, n, i + 1, n, p[i]);
}
calcAns(0, 0, n);
int lcm = 1;
fore(i, 1, M)
lcm = mul(lcm, binPow(i, baseA[i]));
int add = 0;
fore(i, 0, n)
if(ok[i])
add = 1;
cout << (lcm + add) % MOD << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
precalc();
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Greedy Solution
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int MOD = int(1e9) + 7;
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
int ans = 1;
while(k > 0) {
if(k & 1) ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
const int M = 2000 * 1000 + 555;
int minD[M];
vector<pt> ps[M];
inline void precalc() {
iota(minD, minD + M, 0);
fore(val, 2, M) {
if(minD[val] < val)
continue;
for(li j = val * 1ll * val; j < M; j += val)
minD[j] = min(minD[j], val);
}
fore(i, 2, M) {
int v = i;
ps[i].clear();
while(v > 1) {
int md = minD[v];
if(ps[i].empty() || ps[i].back().x != md)
ps[i].emplace_back(md, 0);
ps[i].back().y++;
v /= md;
}
}
}
int n;
vector<int> p;
inline bool read() {
if(!(cin >> n))
return false;
p.assign(n, 0);
fore(i, 0, n)
assert(scanf("%d", &p[i]) == 1);
return true;
}
int a[M], cnt[M];
inline void solve() {
sort(p.begin(), p.end(), greater<int>());
for(int& cp : p) {
if(a[cp] == 0) {
a[cp] = 1;
cnt[cp] = 1;
} else {
cp--;
for(auto np : ps[cp]) {
if(a[np.x] < np.y) {
a[np.x] = np.y;
cnt[np.x] = 1;
} else if(a[np.x] == np.y)
cnt[np.x]++;
}
}
}
int add = 0;
for(int cp : p) {
bool un = false;
for(auto np : ps[cp])
un |= (a[np.x] == np.y && cnt[np.x] == 1);
if(!un)
add = 1;
}
int lcm = 1;
fore(i, 2, M)
lcm = mul(lcm, binPow(i, a[i]));
cout << (lcm + add) % MOD << endl;
}
int main(){
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int t = clock();
#endif
cout << fixed << setprecision(10);
precalc();
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - t << endl;
#endif
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define PII pair <int, int>
const int N = 1e6 + 7;
int n;
int in[N];
int ans[N];
bool used[N];
vector <int> unused;
int cnt;
deque <PII> cur;
vector <PII> getEqual;
set <int> S;
vector <int> place[N];
vector <pair <int, int> > order;
bool check(){
if(in[1] != 0 && in[n + n - 1] != 0 && in[1] != in[n + n - 1])
return false;
for(int i = 1; i + 1 < n + n; ++i)
if(in[i] == in[i + 1] && in[i] != 0)
return false;
for(int i = 1; i < n + n; ++i){
if(in[i] == 0)
continue;
if(place[in[i]].size() == 0)
order.push_back({i, in[i]});
place[in[i]].push_back(i);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j < place[i].size(); ++j)
if(place[i][j]%2 != place[i][j - 1]%2)
return false;
S.insert(n + n);
sort(order.begin(), order.end());
for(auto v: order){
auto it = S.lower_bound(v.first);
if(*it < place[v.second].back())
return false;
for(int c: place[v.second])
S.insert(c);
}
return true;
}
inline int get(){
if(unused.size() == 0){
puts("no");
exit(0);
}
int ret = unused.back();
unused.pop_back();
return ret;
}
void go(){
deque <PII> help;
while(help.size() + cur.size() >= 3){
if(help.size() < 3){
help.push_back(cur.front());
cur.pop_front();
continue;
}
PII v1 = help.back(); help.pop_back();
PII v2 = help.back(); help.pop_back();
PII v3 = help.back(); help.pop_back();
if(v1.st == 0 && v2.st != 0 && v3.st != 0){
ans[v1.nd] = v3.st;
help.push_back(v3);
}
else{
help.push_back(v3);
help.push_back(v2);
help.push_back(v1);
}
if(cur.size() == 0)
break;
help.push_back(cur.front());
cur.pop_front();
}
while(help.size()){
cur.push_back(help.front());
help.pop_front();
}
}
void solve(int root){
int need = (cur.size() + 1) / 2 - cnt;
if(need < 0){
puts("no");
exit(0);
}
deque <PII> help;
while(cur.size()){
auto v = cur.front();
cur.pop_front();
if(need > 0 && v.st == 0){
--need;
v.st = get();
ans[v.nd] = v.st;
}
help.push_back(v);
}
while(help.size()){
cur.push_front(help.front());
help.pop_front();
}
go();
if(root == -1 && cur.back().st == 0){
root = cur.front().st;
ans[cur.back().nd] = root;
cur.pop_front();
cur.pop_back();
solve(root);
return;
}
reverse(cur.begin(), cur.end());
go();
while(cur.size() > 0){
auto v = cur.front();
cur.pop_front();
if(v.st == 0)
ans[v.nd] = root;
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i < n + n; ++i){
scanf("%d", &in[i]);
used[in[i]] = true;
}
if(!check()){
puts("no");
return 0;
}
if(in[1] != 0)
in[n + n - 1] = in[1];
else if(in[n + n - 1] != 0)
in[1] = in[n + n - 1];
for(int i = 1; i <= n; ++i){
if(!used[i])
unused.push_back(i);
used[i] = false;
}
for(int i = 1; i < n + n; ++i)
ans[i] = in[i];
for(int i = 1; i < n + n; ++i){
if(in[i] == 0){
getEqual.push_back({in[i], i});
continue;
}
if(used[in[i]]){
cnt = 0;
while(getEqual.back().st != in[i]){
if(getEqual.back().st > 0){
++cnt;
used[getEqual.back().st] = false;
}
cur.push_front(getEqual.back());
getEqual.pop_back();
}
solve(in[i]);
continue;
}
getEqual.push_back({in[i], i});
used[in[i]] = true;
}
cnt = 0;
while(getEqual.size()){
if(getEqual.back().st > 0){
++cnt;
used[getEqual.back().st] = false;
}
cur.push_front(getEqual.back());
getEqual.pop_back();
}
solve(-1);
puts("yes");
for(int i = 1; i < n + n; ++i)
printf("%d%c", ans[i], i == n + n - 1 ? '\n' : ' ');
return 0;
}