Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n = int(input())
a = list(map(int, input().split()))
if a[0] == a[n - 1]:
print('NO')
else:
print('YES')
print(a[n - 1], end = ' ')
print(*(a[0:n-1]))
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n));
int l = 1, r = n * n, t = 0;
forn(i, n) {
forn(j, n) {
if (t) a[i][j] = l++;
else a[i][j] = r--;
t ^= 1;
}
if (i & 1) reverse(a[i].begin(), a[i].end());
}
forn(i, n) forn(j, n) cout << a[i][j] << " \n"[j == n - 1];
}
}
1783C - Yet Another Tournament
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &x : a) cin >> x;
auto b = a;
sort(b.begin(), b.end());
int ans = 0;
for (int i = 0; i < n && b[i] <= m; ++i) {
m -= b[i];
++ans;
}
if (ans != 0 && ans != n && m + b[ans - 1] >= a[ans]) ++ans;
cout << n + 1 - ans << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
const int ZERO = 100000;
int dp[2][ZERO * 2];
void recalc(int x)
{
for(int i = 0; i < ZERO * 2; i++)
dp[1][i] = 0;
for(int i = 0; i < ZERO * 2; i++)
{
if(dp[0][i] == 0) continue;
int nx = x + i;
dp[1][nx] = add(dp[1][nx], dp[0][i]);
if(nx != ZERO)
dp[1][2 * ZERO - nx] = add(dp[1][2 * ZERO - nx], dp[0][i]);
}
for(int i = 0; i < ZERO * 2; i++)
dp[0][i] = dp[1][i];
}
int main()
{
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
dp[0][ZERO] = 1;
for(int i = 1; i + 1 < n; i++)
recalc(a[i]);
int ans = 0;
for(int i = 0; i < ZERO * 2; i++)
ans = add(ans, dp[0][i]);
cout << ans << endl;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--){
int n;
scanf("%d", &n);
vector<int> a(n), b(n);
forn(i, n) scanf("%d", &a[i]);
forn(i, n) scanf("%d", &b[i]);
vector<int> dx(n + 1);
forn(i, n) if (b[i] < a[i]){
++dx[b[i]];
--dx[a[i]];
}
forn(i, n) dx[i + 1] += dx[i];
vector<int> ans;
for (int k = 1; k <= n; ++k){
bool ok = true;
for (int nk = k; nk <= n; nk += k)
ok &= dx[nk] == 0;
if (ok)
ans.push_back(k);
}
printf("%d\n", int(ans.size()));
for (int k : ans) printf("%d ", k);
puts("");
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 5043;
vector<int> g[N];
int mt[N];
int u[N];
vector<vector<int>> cycle[2];
vector<int> a[2];
int n;
int vs[2];
vector<vector<int>> inter;
bool kuhn(int x)
{
if(u[x]) return false;
u[x] = true;
for(auto y : g[x])
{
if(mt[y] == x) continue;
if(mt[y] == -1 || kuhn(mt[y]))
{
mt[y] = x;
return true;
}
}
return false;
}
int find_intersection(const vector<int>& x, const vector<int>& y)
{
for(auto i : x)
for(auto j : y)
if(i == j)
return i;
return -1;
}
int main()
{
scanf("%d", &n);
for(int k = 0; k < 2; k++)
{
a[k].resize(n);
for(int j = 0; j < n; j++)
{
scanf("%d", &a[k][j]);
a[k][j]--;
}
}
for(int k = 0; k < 2; k++)
{
vector<bool> used(n);
for(int i = 0; i < n; i++)
{
if(used[i]) continue;
vector<int> cur;
int j = i;
while(!used[j])
{
cur.push_back(j);
used[j] = true;
j = a[k][j];
}
cycle[k].push_back(cur);
}
vs[k] = cycle[k].size();
}
inter.resize(vs[0], vector<int>(vs[1]));
for(int i = 0; i < vs[0]; i++)
for(int j = 0; j < vs[1]; j++)
{
inter[i][j] = find_intersection(cycle[0][i], cycle[1][j]);
if(inter[i][j] != -1)
g[i].push_back(j);
}
for(int i = 0; i < vs[1]; i++)
mt[i] = -1;
for(int i = 0; i < vs[0]; i++)
{
for(int j = 0; j < vs[0]; j++)
u[j] = false;
kuhn(i);
}
set<int> res;
for(int i = 0; i < n; i++) res.insert(i);
for(int i = 0; i < vs[1]; i++)
if(mt[i] != -1)
res.erase(inter[mt[i]][i]);
printf("%d\n", res.size());
for(auto x : res) printf("%d ", x + 1);
puts("");
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution 1 (adedalic)
#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 long double ld;
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) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const int LOG = 18;
const int N = int(2e5) + 55;
int n;
vector<int> a;
vector<int> g[N];
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
fore (i, 0, n - 1) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
return true;
}
int p[LOG][N];
int h[N], tin[N], tout[N], T = 0;
void precalcLca(int v, int pr) {
tin[v] = T++;
h[v] = 0;
if (pr != v)
h[v] = h[pr] + 1;
p[0][v] = pr;
fore (pw, 0, LOG - 1)
p[pw + 1][v] = p[pw][p[pw][v]];
for (int to : g[v]) {
if (to == pr)
continue;
precalcLca(to, v);
}
tout[v] = T;
}
bool isParent(int l, int v) {
return tin[l] <= tin[v] && tout[v] <= tout[l];
}
int lca(int u, int v) {
if (isParent(u, v))
return u;
if (isParent(v, u))
return v;
for (int pw = LOG - 1; pw >= 0; pw--)
if (!isParent(p[pw][v], u))
v = p[pw][v];
assert(!isParent(v, u));
assert(isParent(p[0][v], u));
return p[0][v];
}
int getFarthest(int s) {
vector<int> used(n, 0);
queue<int> q;
used[s] = 1;
q.push(s);
int v;
while (!q.empty()) {
v = q.front();
q.pop();
for (int to : g[v]) {
if (used[to])
continue;
used[to] = 1;
q.push(to);
}
}
return v;
}
int getDist(int u, int v) {
return h[u] + h[v] - 2 * h[lca(u, v)];
}
const int M = int(2e5);
vector<pt> ops[4 * M];
void setOp(int v, int l, int r, int lf, int rg, const pt &op) {
if (l >= r || lf >= rg) return;
if (l == lf && r == rg) {
ops[v].push_back(op);
return;
}
int mid = (l + r) / 2;
if (lf < mid)
setOp(2 * v + 1, l, mid, lf, min(mid, rg), op);
if (rg > mid)
setOp(2 * v + 2, mid, r, max(lf, mid), rg, op);
}
void updDiam(int &s, int &t, int &curD, const pt &op) {
int v = op.x;
a[v] = op.y;
int ns = s, nt = t, nD = curD;
vector<pt> cds = {{s, v}, {v, t}, {v, v}};
for (auto &c : cds) {
int d1 = getDist(c.x, c.y);
if (nD < a[c.x] + d1 + a[c.y]) {
nD = a[c.x] + d1 + a[c.y];
ns = c.x, nt = c.y;
}
}
s = ns;
t = nt;
curD = nD;
}
vector<int> ans;
void calcDiams(int v, int l, int r, int s, int t, int curD) {
for (auto &op : ops[v])
updDiam(s, t, curD, op);
if (r - l > 1) {
int mid = (l + r) / 2;
calcDiams(2 * v + 1, l, mid, s, t, curD);
calcDiams(2 * v + 2, mid, r, s, t, curD);
}
else
ans[l] = (curD + 1) / 2;
for (auto &op : ops[v])
a[op.first] = 0;
}
inline void solve() {
precalcLca(0, 0);
int s = getFarthest(0);
int t = getFarthest(s);
int m;
cin >> m;
vector<int> lst(n, 0);
fore (i, 0, m) {
int v, x;
cin >> v >> x;
v--;
setOp(0, 0, m, lst[v], i, {v, a[v]});
lst[v] = i;
a[v] = x;
}
fore (v, 0, n)
setOp(0, 0, m, lst[v], m, {v, a[v]});
ans.resize(m, -1);
a.assign(n, 0);
calcDiams(0, 0, m, s, t, getDist(s, t));
fore (i, 0, m)
cout << ans[i] << '\n';
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Solution 2 (adedalic)
#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 long double ld;
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) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const int LOG = 18;
const int N = int(2e5) + 55;
int n;
vector<int> a;
vector<int> g[N];
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
fore (i, 0, n - 1) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
return true;
}
struct Lca {
vector<int> log2, tin;
vector< vector<int> > hs;
int T = 0;
void dfs(int v, int p, int cdepth) {
tin[v] = T++;
hs[0][tin[v]] = cdepth;
for (int to : g[v]) {
if (to == p)
continue;
dfs(to, v, cdepth + 1);
hs[0][T++] = cdepth;
}
}
void init() {
log2.assign(2 * n, 0);
fore (i, 2, sz(log2))
log2[i] = log2[i / 2] + 1;
hs.assign(log2.back() + 1, vector<int>(2 * n, INF));
tin.assign(n, 0);
T = 0;
dfs(0, -1, 0);
assert(T < 2 * n);
fore (pw, 0, sz(hs) - 1) {
fore (i, 0, T - (1 << pw))
hs[pw + 1][i] = min(hs[pw][i], hs[pw][i + (1 << pw)]);
}
}
int getMin(int u, int v) {
if (tin[u] > tin[v])
swap(u, v);
int len = log2[tin[v] + 1 - tin[u]];
int d = min(hs[len][tin[u]], hs[len][tin[v] + 1 - (1 << len)]);
// cerr << u << " " << v << ": " << d << endl;
return d;
}
inline int getH(int v) {
return hs[0][tin[v]];
}
} lcaST;
int getFarthest(int s) {
vector<int> used(n, 0);
queue<int> q;
used[s] = 1;
q.push(s);
int v;
while (!q.empty()) {
v = q.front();
q.pop();
for (int to : g[v]) {
if (used[to])
continue;
used[to] = 1;
q.push(to);
}
}
return v;
}
int getDist(int u, int v) {
return lcaST.getH(u) + lcaST.getH(v) - 2 * lcaST.getMin(u, v);
}
const int M = int(2e5);
vector<pt> ops[4 * M];
void setOp(int v, int l, int r, int lf, int rg, const pt &op) {
if (l >= r || lf >= rg) return;
if (l == lf && r == rg) {
ops[v].push_back(op);
return;
}
int mid = (l + r) / 2;
if (lf < mid)
setOp(2 * v + 1, l, mid, lf, min(mid, rg), op);
if (rg > mid)
setOp(2 * v + 2, mid, r, max(lf, mid), rg, op);
}
void updDiam(int &s, int &t, int &curD, const pt &op) {
int v = op.x;
a[v] = op.y;
int ns = s, nt = t, nD = curD;
vector<pt> cds = {{s, v}, {v, t}, {v, v}};
for (auto &c : cds) {
int d1 = getDist(c.x, c.y);
if (nD < a[c.x] + d1 + a[c.y]) {
nD = a[c.x] + d1 + a[c.y];
ns = c.x, nt = c.y;
}
}
s = ns;
t = nt;
curD = nD;
}
vector<int> ans;
void calcDiams(int v, int l, int r, int s, int t, int curD) {
for (auto &op : ops[v])
updDiam(s, t, curD, op);
if (r - l > 1) {
int mid = (l + r) / 2;
calcDiams(2 * v + 1, l, mid, s, t, curD);
calcDiams(2 * v + 2, mid, r, s, t, curD);
}
else
ans[l] = (curD + 1) / 2;
for (auto &op : ops[v])
a[op.first] = 0;
}
inline void solve() {
lcaST.init();
int s = getFarthest(0);
int t = getFarthest(s);
int m;
cin >> m;
vector<int> lst(n, 0);
fore (i, 0, m) {
int v, x;
cin >> v >> x;
v--;
setOp(0, 0, m, lst[v], i, {v, a[v]});
lst[v] = i;
a[v] = x;
}
fore (v, 0, n)
setOp(0, 0, m, lst[v], m, {v, a[v]});
ans.resize(m, -1);
a.assign(n, 0);
calcDiams(0, 0, m, s, t, getDist(s, t));
fore (i, 0, m)
cout << ans[i] << '\n';
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}