Author: FelixMP Preparator: FelixMP
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int minv = 1e9+1;
int maxv = -1;
int mini;
int maxi;
for(int i=0; i < n; ++i) {
int a;
cin >> a;
if(a > maxv) {
maxi = i+1;
maxv = a;
}
if(a < minv) {
mini = i+1;
minv = a;
}
}
cout << mini << " " << maxi << endl;
}
}
Author: FelixMP Preparator: xpov1LL
Solution
Tutorial is loading...
Code
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n, a;
cin >> n >> a;
vector<int> v(n);
for(int& x : v) cin >> x;
bool ans = false;
if(n == 1) ans = (v[0] == a);
else {
sort(v.begin(), v.end());
int i = 0;
int j = 1;
while(j < n and i < n) {
if(v[i] + abs(a) == v[j]) {
ans = true;
break;
}
else if(v[i] + abs(a) < v[j]) ++i;
else ++j;
}
}
cout << (ans? "YES" : "NO") << '\n';
}
}
Author: FelixMP Preparator: FelixMP
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vi a(n);
for(int i=0; i < n; ++i) cin >> a[i];
sort(a.begin(), a.end());
bool one = false;
bool consec = false;
for(int i=0; i < n; ++i) {
if(a[i] == 1) one = true;
if(i < n-1 && a[i]+1 == a[i+1]) consec = true;
}
cout << ((one && consec) ? "NO" : "YES") << endl;
}
}
Author: FelixMP Preparator: FelixMP
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--) {
ll n;
cin >> n;
ll x = n;
while(x % 2 == 0) x /= 2;
if(x == 1) {
cout << -1 << endl;
}
else if(x <= 2e9 && (x*(x+1))/2 <= n) {
cout << x << endl;
}
else {
cout << 2*(n/x) << endl;
}
}
}
Author: FelixMP Preparator: FelixMP
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
vvi al;
vi ans;
void dfs(int u, int p, int c) {
ans[u] = ((int)al[u].size())*c;
for(int v : al[u]) {
if(v != p) {
dfs(v, u, -c);
}
}
}
int main() {
int T;
cin >> T;
while(T--) {
int n;
cin >> n;
al = vvi(n);
for(int i=0; i < n-1; ++i) {
int u, v;
cin >> u >> v;
u--;
v--;
al[u].push_back(v);
al[v].push_back(u);
}
ans = vi(n);
dfs(0, -1, 1);
for(int i=0; i < n; ++i) {
cout << ans[i];
if(i < n-1) cout << " ";
}
cout << endl;
}
}
Author: FelixMP Preparator: FelixMP
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
int main() {
int T;
cin >> T;
while(T--) {
ll n;
cin >> n;
vi a(n);
ll tsum = 0;
for(int i=0; i < n; ++i) {
cin >> a[i];
tsum += a[i];
}
sort(a.begin(), a.end());
if(a[n-1]*(n-2) + tsum < 0 || a[0]*(n-2) + tsum > 0) {
cout << "INF" << endl;
continue;
}
ll cslope = a[n-1]*(n-2) + tsum;
ll cvalue = -(n-1)*a[n-1]*a[n-1];
ll ans = cvalue;
for(ll i=1; i < n; ++i) {
ll d = a[n-i]-a[n-i-1];
cvalue += cslope*d;
ans = max(cvalue, ans);
cslope += a[0]-a[n-1];
}
cout << ans << endl;
}
}
Author: FelixMP Preparator: FelixMP
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
vi obtain_p_permutation(const vi& a) {
int n = a.size();
vi pp(n, -1);
vi p(n);
int cp = 0;
vi cnt(n);
for(int i=0; i < n; ++i) {
cnt[a[i]]++;
}
for(int i=0; i < n; ++i) {
if(pp[a[i]] == -1) {
if(cnt[a[i]] == 1) {
p[i] = n/2;
}
else {
p[i] = cp;
pp[a[i]] = n-cp-1;
cp++;
cnt[a[i]]--;
}
}
else {
p[i] = pp[a[i]];
pp[a[i]] = -1;
cnt[a[i]]--;
}
}
return p;
}
vvi find_cycles(vi p, vi& in_cyc) {
int n = p.size();
vi vis = vi(n);
vvi cycles;
for(int i=0; i < n; ++i) {
if(!vis[i]) {
vi cyc;
int v = i;
while(!vis[v]) {
cyc.push_back(v);
in_cyc[v] = cycles.size();
vis[v] = true;
v = p[v];
}
cycles.push_back(cyc);
}
}
return cycles;
}
int find_set(vi& dsu, int x) {
if(dsu[x] == x) return x;
return dsu[x] = find_set(dsu, dsu[x]);
}
void solve() {
int n;
cin >> n;
vi a(n);
vi cnt(n);
for(int i=0; i < n; ++i) {
cin >> a[i];
a[i]--;
cnt[a[i]]++;
}
int odd_i = -1;
for(int i=0; i < n; ++i) {
if(cnt[i]%2 == 1) {
if(odd_i == -1) {
odd_i = i;
}
else {
odd_i = -2;
}
}
}
if(odd_i == -2) {
cout << "NO" << endl;
}
else if(odd_i != -1 && (cnt[odd_i] == 1 && odd_i == a[n/2])) {
cout << "NO" << endl;
}
else {
vi p = obtain_p_permutation(a);
if(odd_i != -1 && p[n/2] == n/2) {
for(int i=0; i < n; ++i) {
if(i != n/2 && a[i] == odd_i) {
p[n/2] = p[i];
p[i] = n/2;
break;
}
}
}
vi rp(n);
for(int i=0; i < n; ++i) {
rp[p[i]] = i;
}
vvi cycles;
vi in_cyc(n);
cycles = find_cycles(p, in_cyc);
vi dsu(n);
for(int i=0; i < n; ++i) dsu[i] = i;
for(int i=0; i < n; ++i) {
if(find_set(dsu, in_cyc[i]) != find_set(dsu, in_cyc[n-i-1])) {
dsu[find_set(dsu, in_cyc[i])] = find_set(dsu, in_cyc[n-i-1]);
int j1 = rp[i];
int j2 = rp[n-i-1];
p[j2] = i;
rp[i] = j2;
p[j1] = n-i-1;
rp[n-i-1] = j1;
}
}
cycles = find_cycles(p, in_cyc);
int nc = cycles.size();
vi prev_p = vi(p);
vi prev_rp = vi(rp);
for(int i=0; i < nc-1; ++i) {
int i0 = cycles[i][0];
int ip1 = cycles[(i+1)][0];
p[prev_rp[n-i0-1]] = ip1;
rp[ip1] = prev_rp[n-i0-1];
}
p[prev_rp[n-cycles[nc-1][0]-1]] = n-cycles[0][0]-1;
rp[n-cycles[0][0]-1] = prev_rp[n-cycles[nc-1][0]-1];
for(int i=0; i < nc-1; ++i) {
int i0 = cycles[i][0];
int ip1 = cycles[(i+1)][0];
p[prev_rp[i0]] = n-ip1-1;
rp[n-ip1-1] = prev_rp[i0];
}
p[prev_rp[cycles[nc-1][0]]] = cycles[0][0];
rp[cycles[0][0]] = prev_rp[cycles[nc-1][0]];
cout << "YES" << endl;
for(int i=0; i < n; ++i) {
cout << rp[i]+1 << " ";
}
cout << endl;
}
}
int main() {
int T;
cin >> T;
while(T--) {
solve();
}
}
Author: FelixMP Preparator: FelixMP
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
ll read_ll() {
string s;
cin >> s;
ll x = 0;
for(int i=0; i < (int)s.length(); ++i) {
x *= 10;
x += ll(s[i]-'0');
}
return x;
}
void print_ll(ll x) {
vector<int> p;
while(x > 0) {
p.push_back((int)(x%10));
x /= 10;
}
reverse(p.begin(), p.end());
for(int y : p) cout << y;
}
inline ll ctz(ll x) {
long long a = x&((ll(1)<<ll(63))-ll(1));
long long b = x>>ll(63);
if(a == 0) return ll(63)+__builtin_ctzll(b);
return __builtin_ctzll(a);
}
inline ll abll(ll x) {
return x >= 0 ? x : -x;
}
ll gcd(ll a, ll b) {
if(b == 0) return a;
if(a == 0) return b;
int az = ctz(a);
int bz = ctz(b);
int shift = min(az, bz);
b >>= bz;
while(a != 0) {
a >>= az;
ll diff = b-a;
if(diff) az = ctz(diff);
b = min(a, b);
a = abll(diff);
}
return b << shift;
}
void init_st(vi& st, const vi& v) {
int n = v.size();
for(int i=0; i < n; ++i) {
st[n+i] = v[i];
}
for(int i=n-1; i >= 1; --i) {
st[i] = gcd(st[2*i], st[2*i+1]);
}
}
void update_st(vi& st, int i, ll x) {
int n = (int)st.size() / 2;
int pos = n+i;
st[pos] = x;
while(pos > 1) {
pos /= 2;
st[pos] = gcd(st[2*pos], st[2*pos+1]);
}
}
void solve(const vi& a, const vi& b, vector<bool>& ai, vector<bool>& bi) {
int n = a.size();
int m = b.size();
vvi st_a = vvi(n, vi(2*m, 0));
vvi st_b = vvi(m, vi(2*n, 0));
for(int i=0; i < n; ++i) {
vi af(m);
for(int j=0; j < m; ++j) {
af[j] = a[i]/gcd(a[i], b[j]);
}
init_st(st_a[i], af);
}
for(int i=0; i < m; ++i) {
vi bf(n);
for(int j=0; j < n; ++j) {
bf[j] = b[i]/gcd(b[i], a[j]);
}
init_st(st_b[i], bf);
}
queue<int> dq;
for(int i=0; i < n; ++i) {
if(st_a[i][1] > 1) {
dq.push(i);
ai[i] = false;
}
}
for(int i=0; i < m; ++i) {
if(st_b[i][1] > 1) {
dq.push(n+i);
bi[i] = false;
}
}
while(!dq.empty()) {
int idx = dq.front();
dq.pop();
if(idx < n) {
int i = idx;
for(int j=0; j < m; ++j) {
if(bi[j]) {
update_st(st_b[j], i, b[j]);
if(st_b[j][1] > 1) {
dq.push(n+j);
bi[j] = false;
}
}
}
}
else {
int i = idx-n;
for(int j=0; j < n; ++j) {
if(ai[j]) {
update_st(st_a[j], i, a[j]);
if(st_a[j][1] > 1) {
dq.push(j);
ai[j] = false;
}
}
}
}
}
}
int main() {
int T;
cin >> T;
while(T--) {
int n, m;
cin >> n >> m;
vi a(n);
vi b(m);
for(int i=0; i < n; ++i) a[i] = read_ll();
for(int i=0; i < m; ++i) b[i] = read_ll();
vector<bool> ai(n, true);
vector<bool> bi(m, true);
solve(a, b, ai, bi);
int as = 0;
int bs = 0;
for(int i=0; i < n; ++i) {
if(ai[i]) as++;
}
for(int i=0; i < m; ++i) {
if(bi[i]) bs++;
}
if(as == 0 || bs == 0) cout << "NO" << endl;
else {
cout << "YES" << endl;
cout << as << " " << bs << endl;
for(int i=0; i < n; ++i) {
if(ai[i]) {
print_ll(a[i]);
cout << " ";
}
}
cout << endl;
for(int i=0; i < m; ++i) {
if(bi[i]) {
print_ll(b[i]);
cout << " ";
}
}
cout << endl;
}
}
}
Author: FelixMP Preparator: FelixMP
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
struct graph {
int n;
int m;
vvi al;
vi morphism;
vvi dfs_children;
vi dfs_parent;
vi dfs_num;
vi dfs_low;
int dfs_count;
bool is_root_ac = false;
bool bad_biccon = false;
vii repr_edge;
void dt_dfs(int v, int par) {
dfs_parent[v] = par;
dfs_num[v] = dfs_low[v] = dfs_count++;
for(int u : al[v]) {
if(u == par) {
//Nothing
}
else if(dfs_num[u] == -1) {
dfs_children[v].push_back(u);
dt_dfs(u, v);
dfs_low[v] = min(dfs_low[v], dfs_low[u]);
}
else {
dfs_low[v] = min(dfs_low[v], dfs_num[u]);
}
}
}
ii min_repr_edge(ii a, ii b) {
if(a.first == -1) return b;
if(b.first == -1) return a;
if(dfs_num[a.second] < dfs_num[b.second]) return a;
if(dfs_num[a.second] > dfs_num[b.second]) return b;
if(dfs_num[a.first] > dfs_num[b.first]) return a;
if(dfs_num[a.first] < dfs_num[b.first]) return b;
return a;
}
void dt_dfs_hamil(int v) {
repr_edge[v] = ii(-1, -1);
for(int u : dfs_children[v]) {
dt_dfs_hamil(u);
repr_edge[v] = min_repr_edge(repr_edge[v], repr_edge[u]);
}
for(int u : al[v]) {
if(u == dfs_parent[v]) {
//Nothing
}
else if(dfs_num[u] < dfs_num[v]) {
repr_edge[v] = min_repr_edge(repr_edge[v], ii(v, u));
}
}
if(dfs_parent[v] == -1) {
//Root case
//Nothing more to check, repr_edge will always be set correctly.
}
else {
if(dfs_children[v].size() == 0) {
//Nothing to check
}
else if(dfs_children[v].size() == 1) {
//Lemma 4
if(dfs_low[dfs_children[v][0]] != dfs_low[v] && dfs_low[dfs_children[v][0]] != dfs_num[dfs_parent[v]]) {
bad_biccon = true;
}
}
else if(dfs_children[v].size() == 2) {
//Lemma 3
if(dfs_parent[dfs_parent[v]] != -1) {
if(!((dfs_low[dfs_children[v][0]] == dfs_num[dfs_parent[v]]) ^ (dfs_low[dfs_children[v][1]] == dfs_num[dfs_parent[v]]))) {
bad_biccon = true;
}
}
if(dfs_low[v] < min(dfs_low[dfs_children[v][0]], dfs_low[dfs_children[v][1]])) {
bad_biccon = true;
}
}
else {
bad_biccon = true;
}
}
}
void dt_dfs_cedges(vvii& cedges, vii& edge_stack, int v, int par) {
dfs_parent[v] = par;
dfs_num[v] = dfs_low[v] = dfs_count++;
for(int u : al[v]) {
if(u == par) {
//Nothing
}
else if(dfs_num[u] == -1) {
dfs_children[v].push_back(u);
edge_stack.emplace_back(v, u);
dt_dfs_cedges(cedges, edge_stack, u, v);
dfs_low[v] = min(dfs_low[v], dfs_low[u]);
if((par == -1 && is_root_ac) || (par != -1 && dfs_low[u] >= dfs_num[v])) {
vii comp;
while(edge_stack.back().first != v || edge_stack.back().second != u) {
comp.push_back(edge_stack.back());
edge_stack.pop_back();
}
comp.push_back(edge_stack.back());
edge_stack.pop_back();
cedges.push_back(comp);
}
}
else {
dfs_low[v] = min(dfs_low[v], dfs_num[u]);
if(dfs_num[u] < dfs_num[v]) {
edge_stack.emplace_back(v, u);
}
}
}
}
void generate_dfs_tree(int root) {
dfs_children = vvi(n, vi());
dfs_parent = vi(n);
dfs_count = 0;
dfs_num = vi(n, -1);
dfs_low = vi(n, -1);
dt_dfs(root, -1);
}
void generate_edge_partition(vvii& cedges, vii& edge_stack, int root) {
generate_dfs_tree(root);
is_root_ac = (dfs_children[root].size() > 1);
dfs_children = vvi(n, vi());
dfs_parent = vi(n);
dfs_count = 0;
dfs_num = vi(n, -1);
dfs_low = vi(n, -1);
dt_dfs_cedges(cedges, edge_stack, root, -1);
if(!edge_stack.empty()) cedges.push_back(edge_stack);
}
void generate_hamil_dfs_tree(int root) {
generate_dfs_tree(root);
repr_edge = vii(n, ii());
dt_dfs_hamil(root);
}
};
vector<graph> partition_biconnected(graph& g) {
vvii cedges;
vii edge_stack;
g.generate_edge_partition(cedges, edge_stack, 0);
vector<graph> comp;
for(vii& vec : cedges) {
graph h;
h.n = 0;
h.m = vec.size();
unordered_map<int, int> rmorph;
for(ii e : vec) {
if(rmorph.find(e.first) == rmorph.end()) {
rmorph[e.first] = h.n++;
}
if(rmorph.find(e.second) == rmorph.end()) {
rmorph[e.second] = h.n++;
}
}
h.morphism = vi(h.n);
h.al = vvi(h.n);
for(ii e : vec) {
int u = rmorph[e.first];
int v = rmorph[e.second];
h.morphism[u] = g.morphism[e.first];
h.morphism[v] = g.morphism[e.second];
h.al[u].push_back(v);
h.al[v].push_back(u);
}
comp.push_back(h);
}
return comp;
}
void upwards_path(graph& g, vi& hc, int v, int tar);
void downwards_path(graph& g, vi& hc, int v, int tar);
void upwards_path(graph& g, vi& hc, int v, int tar) {
if(g.dfs_children[v].size() == 2) {
int u1 = g.dfs_children[v][0];
int u2 = g.dfs_children[v][1];
if(g.repr_edge[u1] == g.repr_edge[v]) swap(u1, u2);
hc.push_back(v);
downwards_path(g, hc, u1, g.repr_edge[u1].first);
if(v != tar) {
upwards_path(g, hc, g.dfs_parent[v], tar);
}
}
else if(g.dfs_children[v].size() == 1) {
int u = g.dfs_children[v][0];
hc.push_back(v);
if(g.repr_edge[u] != g.repr_edge[v]) {
downwards_path(g, hc, u, g.repr_edge[u].first);
}
if(v != tar) {
upwards_path(g, hc, g.dfs_parent[v], tar);
}
}
else {
hc.push_back(v);
if(v != tar) {
upwards_path(g, hc, g.dfs_parent[v], tar);
}
}
}
void downwards_path(graph& g, vi& hc, int v, int tar) {
if(g.dfs_children[v].size() == 2) {
int u1 = g.dfs_children[v][0];
int u2 = g.dfs_children[v][1];
if(g.repr_edge[u1] == g.repr_edge[v]) swap(u1, u2);
upwards_path(g, hc, g.repr_edge[u1].first, u1);
hc.push_back(v);
downwards_path(g, hc, u2, tar);
}
else if(g.dfs_children[v].size() == 1) {
int u = g.dfs_children[v][0];
if(v == tar) {
upwards_path(g, hc, g.repr_edge[u].first, u);
hc.push_back(v);
}
else {
hc.push_back(v);
downwards_path(g, hc, u, tar);
}
}
else {
hc.push_back(v);
}
}
vi hamiltonian_cycle(graph& g) {
g.generate_hamil_dfs_tree(0);
if(g.bad_biccon) return vi();
vi hc;
downwards_path(g, hc, 0, g.repr_edge[0].first);
assert((int)hc.size() == g.n);
return hc;
}
int comp_index;
bool cyclic_comparator(int a, int b) {
if(a < comp_index) a += 1e7;
if(b < comp_index) b += 1e7;
return a < b;
}
graph sort_graph(const graph& g, const vi& hc) {
graph h;
h.n = g.n;
h.m = g.m;
h.morphism = vi(g.n);
h.al = vvi(g.n);
vi rhc(g.n);
for(int i=0; i < g.n; ++i) {
h.morphism[i] = g.morphism[hc[i]];
rhc[hc[i]] = i;
}
for(int i=0; i < g.n; ++i) {
for(int j : g.al[hc[i]]) {
h.al[i].push_back(rhc[j]);
}
comp_index = i;
//This is m log m, can be improved
sort(h.al[i].begin(), h.al[i].end(), cyclic_comparator);
}
return h;
}
bool has_crossing(const graph& g) {
vii bad_stack;
for(int i=0; i < g.n; ++i) {
comp_index = i;
while(!bad_stack.empty() && i == bad_stack.back().first) bad_stack.pop_back();
for(int j=(int)g.al[i].size()-2; j > 0; --j) {
int u = g.al[i][j];
if(!bad_stack.empty() && cyclic_comparator(bad_stack.back().first, u) && cyclic_comparator(u, bad_stack.back().second)) {
return true;
}
if(u > i && (bad_stack.empty() || u != bad_stack.back().first)) {
bad_stack.emplace_back(u, i);
}
}
}
return false;
}
void merge_ans(const graph& g, vvi& ans) {
for(int i=0; i < g.n; ++i) {
for(int j : g.al[i]) {
ans[g.morphism[i]].push_back(g.morphism[j]);
}
}
}
void merge_single_edge_ans(const graph& g, vvi& ans) {
int u = g.morphism[0];
int v = g.morphism[1];
ans[u].push_back(v);
ans[v].push_back(u);
}
vvi solve(graph& input_graph) {
vvi ans(input_graph.n);
vector<graph> components = partition_biconnected(input_graph);
for(graph g : components) {
if(g.n == 1) {
//Nothing
}
else if(g.n == 2) {
merge_single_edge_ans(g, ans);
}
else {
vi hc = hamiltonian_cycle(g);
if(hc.empty()) {
return vvi();
}
graph g2 = sort_graph(g, hc);
if(has_crossing(g2)) return vvi();
merge_ans(g2, ans);
}
}
return ans;
}
graph read_graph() {
graph g;
int n, m;
cin >> n >> m;
g.n = n;
g.m = m;
g.al = vvi(n, vi());
g.morphism = vi(n, 0);
for(int i=0; i < n; ++i) {
g.morphism[i] = i;
}
for(int i=0; i < m; ++i) {
int u, v;
cin >> u >> v;
g.al[u].push_back(v);
g.al[v].push_back(u);
}
return g;
}
void print_ans(const vvi& ans) {
int n = ans.size();
if(n == 0) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
for(int i=0; i < n; ++i) {
for(int x : ans[i]) {
cout << x << " ";
}
cout << endl;
}
}
}
int main() {
int T;
cin >> T;
while(T--) {
graph input_graph = read_graph();
vvi ans = solve(input_graph);
print_ans(ans);
}
}