Problems A, B, C, D1 and E were authored by me and Adam_GS authored D2 and F.
Hint
If $$$k$$$ is greater or equal to $$$2$$$ you can always swap adjacent elements.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
int arr[n];
for(int i = 0;i < n;i++){
cin>>arr[i];
}
if(is_sorted(arr,arr+n) || k > 1){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
return 0;
}
Hint
Think of each bit independently.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int m[n][n];
int arr[n];
for(int i = 0;i < n;i++){
arr[i] = (1<<30) - 1;
}
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
cin>>m[i][j];
if(i != j){
arr[i] &= m[i][j];
arr[j] &= m[i][j];
}
}
}
bool ok = true;
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(i != j && (arr[i] | arr[j]) != m[i][j]){
ok = false;
}
}
}
if(!ok){
cout<<"NO\n";
}
else{
cout<<"YES\n";
for(int i = 0;i < n;i++){
cout<<arr[i]<<" ";
}
cout<<"\n";
}
}
}
Hint
Think of suffixes.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n];
long long suf[n+1] = {0};
for(int i = 0;i < n;i++){
cin>>arr[i];
}
for(int i = n-1;i >= 0;i--){
suf[i] = suf[i+1] + arr[i];
}
long long ans = suf[0];
for(int i = 1;i < n;i++){
if(suf[i] > 0){
ans += suf[i];
}
}
cout<<ans<<"\n";
}
}
1903D1 - Maximum And Queries (easy version)
Hint
Try using greedy to construct the answer bit by bit.
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
ll T[LIM], P[LIM], n, k;
void solve() {
rep(i, n) T[i]=P[i];
ll ans=0;
for(ll i=60; i>=0; --i) {
ll sum=0;
rep(j, n) {
if(T[j]&(1ll<<i)) continue;
ll p=(T[j]/(1ll<<i))*(1ll<<i)+(1ll<<i);
p+=ans^(p&ans);
sum+=p-T[j];
if(sum > k){
break;
}
}
if(sum>k) continue;
rep(j, n) {
if(T[j]&(1ll<<i)) continue;
ll p=(T[j]/(1ll<<i))*(1ll<<i)+(1ll<<i);
p+=ans^(p&ans);
T[j]=p;
}
ans+=1ll<<i;
k-=sum;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int q;
cin >> n >> q;
rep(i, n) cin >> P[i];
while(q--) {
cin >> k;
solve();
}
}
1903D2 - Maximum And Queries (hard version)
Hint
Try optimizing the greedy approach from $$$O$$$($$$n$$$) to $$$O$$$($$$1$$$).
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7;
ll dpsum[1<<20][20], dpcnt[1<<20], T[LIM];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
ll n, q;
cin >> n >> q;
ll sto=0, sfrom=0;
rep(i, n) {
cin >> T[i];
sto+=(1ll<<20ll)-T[i];
sfrom+=T[i];
++dpcnt[T[i]];
ll sum=0;
rep(j, 20) {
sum+=T[i]&(1ll<<j);
dpsum[T[i]][j]+=sum;
}
}
rep(i, 20) rep(j, 1<<20) if(!(j&(1<<i))) dpcnt[j]+=dpcnt[j+(1<<i)];
rep(i, 20) rep(j, 1<<20) if(!(j&(1<<i))) rep(l, 20) dpsum[j][l]+=dpsum[j+(1<<i)][l];
while(q--) {
ll k;
cin >> k;
if(k>=sto) {
k+=sfrom;
cout << k/n << '\n';
continue;
}
ll ans=0;
for(ll i=19; i>=0; --i) {
ll x=(n-dpcnt[ans|(1<<i)])*(1ll<<i);
x-=dpsum[ans][i]-dpsum[ans|(1<<i)][i];
if(x<=k) {
k-=x;
ans|=1<<i;
}
}
cout << ans << '\n';
}
}
Hint
Do mod $$$2$$$ in all coordinates and see how many different types of points you have in the end.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int sx,sy;
cin>>sx>>sy;
int x[n],y[n];
set<int>p[2];
for(int i = 0;i < n;i++){
cin>>x[i]>>y[i];
p[(x[i] % 2) ^ (y[i] % 2)].insert(i+1);
}
int v = (sx % 2) ^ (sy % 2);
if(p[v].size() >= p[v^1].size()){
cout<<"First"<<endl;
v ^= 1;
for(int i = 0;i < n;i++){
if(i % 2 == 0){
int j;
if(!p[v].empty()){
j = (*p[v].begin());
p[v].erase(j);
}
else{
j = (*p[v^1].begin());
p[v^1].erase(j);
}
cout<<j<<endl;
}
else{
int j;
cin>>j;
if(p[0].count(j)){
p[0].erase(j);
}
else{
p[1].erase(j);
}
}
}
}
else{
cout<<"Second"<<endl;
for(int i = 0;i < n;i++){
if(i % 2 == 1){
int j;
if(!p[v].empty()){
j = (*p[v].begin());
p[v].erase(j);
}
else{
j = (*p[v^1].begin());
p[v^1].erase(j);
}
cout<<j<<endl;
}
else{
int j;
cin>>j;
if(p[0].count(j)){
p[0].erase(j);
}
else{
p[1].erase(j);
}
}
}
}
}
}
Hint
Use binary search the answer and 2-sat.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
vector<vector<ll> >adj,rev;
vector<ll>order;
vector<ll>vis,comp;
ll c;
ll cur;
ll val(ll idx,bool v){
return cur + (2 * idx + v);
}
void dfs1(ll idx){
vis[idx] = true;
for(auto x:adj[idx]){
if(!vis[x]){
dfs1(x);
}
}
order.pb(idx);
}
void dfs2(ll idx){
comp[idx] = c;
for(auto x:rev[idx]){
if(!comp[x]){
dfs2(x);
}
}
}
void build(ll s,ll e,ll idx){
if(s == e){
adj[idx].pb(val(s,0));
rev[val(s,0)].pb(idx);
return;
}
ll mid = (s+e)/2;
build(s,mid,idx*2);
build(mid+1,e,idx*2+1);
adj[idx].pb(idx*2);
adj[idx].pb(idx*2+1);
rev[idx*2].pb(idx);
rev[idx*2+1].pb(idx);
}
void update(ll s,ll e,ll qs,ll qe,ll idx,ll k){
if(qs <= s && e <= qe){
adj[val(k,1)].pb(idx);
rev[idx].pb(val(k,1));
return;
}
if(s > qe || qs > e){
return;
}
ll mid = (s+e)/2;
update(s,mid,qs,qe,idx*2,k);
update(mid+1,e,qs,qe,idx*2+1,k);
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t;
cin>>t;
while(t--){
ll n,m;
cin>>n>>m;
ll u[m],v[m];
f(i,0,m){
cin>>u[i]>>v[i];
}
ll l = 1,r = n;
ll ans = 1;
cur = 4*n;
while(l <= r){
ll mid = (l+r)/2;
order.clear();
vis.assign(6*n+5,0);
comp.assign(6*n+5,0);
adj.assign(6*n+5,vector<ll>());
rev.assign(6*n+5,vector<ll>());
f(i,0,m){
adj[val(u[i],0)].pb(val(v[i],1));
adj[val(v[i],0)].pb(val(u[i],1));
rev[val(u[i],1)].pb(val(v[i],0));
rev[val(v[i],1)].pb(val(u[i],0));
}
build(1,n,1);
f(k,1,n+1){
ll l = max(1,k - mid + 1),r = k-1;
update(1,n,l,r,1,k);
l = k+1;
r = min(n,k + mid - 1);
update(1,n,l,r,1,k);
}
bool ok = true;
c = 1;
f(i,1,n+1){
if(!vis[val(i,0)]){
dfs1(val(i,0));
}
if(!vis[val(i,1)]){
dfs1(val(i,1));
}
}
reverse(order.begin(),order.end());
for(auto x:order){
if(!comp[x]){
dfs2(x);
c++;
}
}
f(i,1,n+1){
ok &= comp[val(i,0)] != comp[val(i,1)];
}
if(ok){
l = mid + 1;
ans = max(ans,mid);
}
else{
r = mid - 1;
}
}
cout<<ans<<"\n";
}
}
jeroenodb's solution O(M log N)
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<basic_string<int>> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
template<int (*merge)(int,int), int (*init)(int)> struct DSU{
vi sz, dat;
DSU(int n) : sz(n,-1),dat(n) {
for(int i=0;i<n;++i) dat[i] = init(i);
}
void link(int a, int b) {
if(sz[a]>sz[b]) {
swap(a,b);
}
sz[a]+=sz[b];
sz[b]=a;
dat[a] = merge(dat[a],dat[b]);
}
bool unite(int a, int b) {
int pa = find(a),pb = find(b);
if(pa!=pb) link(pa,pb);
return pa!=pb;
}
int get(int i) {
return dat[find(i)];
}
int find(int a) {
if(sz[a]<0) return a;
return sz[a] = find(sz[a]);
}
};
int dec(int i) {return i-1;}
int inc(int i) {return i+1;}
int mymin(int a, int b) {return min(a,b);}
int mymax(int a, int b) {return max(a,b);}
bool solve(const vvi& adj, const vvi& rev, int mid) {
int n = rev.size()/2;
DSU<mymin, dec> dsuL(n);
DSU<mymax, inc> dsuR(n);
auto getL = [&](int i) {
if(i>=n) i-=n;
int l = dsuL.get(i);
if(l==-1 or abs(i-l)>=mid) return 0;
return l+1;
};
auto getR = [&](int i) {
if(i>=n) i-=n;
int r = dsuR.get(i);
if(r==n or abs(i-r)>=mid) return 0;
return r+1;
};
auto rem = [&](int at) {
if(at>=n) at-=n;
if(at) dsuR.unite(at-1,at);
if(at+1<n) dsuL.unite(at,at+1);
};
vector<bool> vis(n*2);
vi ord;
auto dfs = [&](auto&& self, int at) -> void {
vis[at]=1;
if(at<n) {
while(int l = getL(at)) self(self,l-1+n);
while(int r = getR(at)) self(self,r-1+n);
} else rem(at);
for(int to : adj[at]) if(!vis[to]) self(self,to);
ord.push_back(at);
};
for(int i=0;i<2*n;++i) if(!vis[i]) dfs(dfs,i);
reverse(all(ord));
fill(all(vis),0);
dsuL = DSU<mymin,dec>(n);
dsuR = DSU<mymax,inc>(n);
int comp=0;
vi comps(2*n);
auto dfs2 = [&](auto&& self, int at) -> void {
comps[at]=comp;
vis[at]=1;
if(at>=n) {
while(int l = getL(at)) self(self,l-1);
while(int r = getR(at)) self(self,r-1);
} else rem(at);
for(int to : rev[at]) if(!vis[to]) self(self,to);
};
for(int i : ord) if(!vis[i]) {
dfs2(dfs2,i);
comp++;
}
for(int i=0;i<n;++i) if(comps[i]==comps[i+n]) return false;
return true;
}
void solve() {
int n,m; cin >> n >> m;
vvi adj(2*n),rev(2*n);
auto addE = [&](int u, int v) {
adj[u].push_back(v);
rev[v].push_back(u);
};
for(int i=0;i<m;++i) {
int u,v; cin >> u >> v;
--u,--v;
addE(u+n,v);
addE(v+n,u);
}
int lo=1,hi=n;
while(lo<hi) {
int mid = (lo+hi+1)/2;
if(solve(adj,rev,mid)) {
lo= mid;
} else hi = mid-1;
}
cout << lo << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while(t--) solve();
}