In yesterday's Codeforces Round 769 (Div. 2), I was falsely accused of plagiarism where as none of the people in question have codes similar to one another.
I received the following message.
Problem C
Problem D
Submissions of all the users for Problem C.
codebuster_10
#include <bits/stdc++.h>
#define int int64_t //be careful about this
using namespace std;
namespace IN{
template<class T> void read(vector<T> &A);
template<class S,class T> void read(pair<S,T> &A);
template<class T,size_t N> void read(array<T,N> &A);
template<class T> void read(T& x){
cin >> x;}
template<class H, class... T> void read(H& h, T&... t){
read(h); read(t...);}
template<class T> void read(vector<T> &A){
for(auto& x : A) read(x);}
template<class S,class T> void read(pair<S,T> &A){
read(A.first); read(A.second);}
template<class T,size_t N> void read(array<T,N> &A){
for(int i = 0; i < N; ++i) read(A[i]);}
}
namespace OUT{
template<typename T>
void __p(T a) {
cout<<a;
}
template<typename T, typename F>
void __p(pair<T, F> a) {
cout<<"{";
__p(a.first);
cout<<",";
__p(a.second);
cout<<"}\n";
}
template<typename T, size_t N>
void __p(array<T,N> a){
cout<<"{";
for(int i = 0; i < N; ++i)
__p(a[i]),cout<<",}\n"[i+1==N];
}
template<typename T>
void __p(std::vector<T> a) {
cout<<"{";
for(auto it=a.begin(); it<a.end(); it++)
__p(*it),cout<<",}\n"[it+1==a.end()];
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
__p(a1);
__p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
cout<<name<<" : ";
__p(arg1);
cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
int bracket=0,i=0;
for(;; i++)
if(names[i]==','&&bracket==0)
break;
else if(names[i]=='(')
bracket++;
else if(names[i]==')')
bracket--;
const char *comma=names+i;
cout.write(names,comma-names)<<" : ";
__p(arg1);
cout<<" | ";
__f(comma+1,args...);
}
#define trace(...) cout<<"Line:"<<__LINE__<<" ", __f(#__VA_ARGS__, __VA_ARGS__)
}
namespace FUN{
void IO(string s = ""){
ios_base::sync_with_stdio(NULL);
cin.tie(nullptr);
cout.precision(20);
cout << fixed;
if(!s.empty()){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
const auto start_time = chrono::high_resolution_clock::now();
void output_run_time(){
// will work for ac,cc&&cf.
#ifndef ONLINE_JUDGE
auto end_time = chrono::high_resolution_clock::now();
chrono::duration<double> diff = end_time-start_time;
cout << "\n\n\nTime Taken : " << diff.count();
#endif
}
template<class T> bool ckmin(T& a, const T b) { return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T b) { return a < b ? a = b, 1 : 0;}
}
using namespace IN;
using namespace OUT;
using namespace FUN;
template<class T>
struct basic_segment_tree {
const T ID = 0;
T comb(T a, T b){// comb(ID,b) = b
return __gcd(a,b);
}
int n; vector<T> seg;
void init(int _n){
n = _n; seg.assign(2 * n,ID);
}
void pull(int p){
seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
}
void upd(int p, T val){ // update val at position p
seg[p += n] = val;
for(p /= 2; p; p /= 2) pull(p);
}
T query(int l, int r){ // query on interval [l, r]
T ra = ID, rb = ID;
for(l += n, r += n+1; l < r; l /= 2, r /= 2){
if(l&1) ra = comb(ra,seg[l++]);
if(r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
template<typename T>
struct fenwick_tree{
int tree_n = 0;
T tree_sum = 0;
vector<T> tree;
fenwick_tree(int n = -1){
if(n >= 0)
init(n);
}
static int highest_bit(int x){
return x == 0 ? -1 : 31 - __builtin_clz(x);
}
void init(int n) {
tree_n = n;
tree_sum = 0;
tree.assign(tree_n + 1, 0);
}
// O(n) initialization of the Fenwick tree.
template<typename T_array>
void build(const T_array &initial){
assert(int(initial.size()) == tree_n);
tree_sum = 0;
for(int i = 1; i <= tree_n; i++){
tree[i] = initial[i-1];
tree_sum += initial[i-1];
for(int k = (i & -i) >> 1; k > 0; k >>= 1)
tree[i] += tree[i - k];
}
}
// index is in [0, tree_n).
void update(int index, const T &change){
assert(0 <= index && index < tree_n);
tree_sum += change;
for(int i = index + 1; i <= tree_n; i += i & -i)
tree[i] += change;
}
// Returns the sum of the range [0, count).
T query(int count) const {
count = min(count, tree_n);
T sum = 0;
for(int i = count; i > 0; i -= i & -i)
sum += tree[i];
return sum;
}
// Returns the sum of the range [start, tree_n).
T query_suffix(int start) const {
return tree_sum - query(start);
}
// Returns the sum of the range [a, b).
T query(int a, int b) const {
return query(b) - query(a);
}
// Returns the element at index a in O(1) amortized across every index. Equivalent to query(a, a + 1).
T get(int a) const {
assert(0 <= a && a < tree_n);
int above = a + 1;
T sum = tree[above];
above -= above & -above;
while (a != above){
sum -= tree[a];
a -= a & -a;
}
return sum;
}
bool set(int index, T value){
assert(0 <= index && index < tree_n);
T current = get(index);
if(current == value)
return false;
update(index, value - current);
return true;
}
// Returns the largest p in `[0, tree_n]` such that `query(p) <= sum`. Returns -1 if no such p exists (`sum < 0`).
// Can be used as an ordered set/multiset on indices in `[0, tree_n)` by using the tree as a 0/1 or frequency array:
// `set(index, 1)` is equivalent to insert(index). `update(index, +1)` is equivalent to multiset.insert(index).
// `set(index, 0)` or `update(index, -1)` are equivalent to erase(index).
// `get(index)` provides whether index is present or not, or the count of index (if multiset).
// `query(index)` provides the count of elements < index.
// `find_last_prefix(k)` finds the k-th smallest element (0-indexed). Returns `tree_n` for `sum >= set.size()`.
int find_last_prefix(T sum) const {
if(sum < 0)
return -1;
int prefix = 0;
for(int k = highest_bit(tree_n); k >= 0; k--)
if(prefix + (1 << k) <= tree_n && tree[prefix + (1 << k)] <= sum){
prefix += 1 << k;
sum -= tree[prefix];
}
return prefix;
}
};
signed main(){
IO();
int n;
read(n);
vector<int> a(n);
read(a);
basic_segment_tree<int> st;
st.init(n);
for(int i = 0; i < n; ++i)
st.upd(i,a[i]);
vector<int> ends(n,-1);
for(int i = 0; i < n; ++i){
int lo = i, hi = n;
while(hi - lo > 1){
int mid = (hi + lo)/2;
st.query(i,mid) - (mid - i + 1) >= 0 ? lo = mid : hi = mid;
}
if(st.query(i,lo) == (lo - i + 1))
ends[lo] = i;
}
fenwick_tree<int> ft;
ft.init(n);
int ans = 0;
for(int i = 0; i < n; ++i){
if(ends[i] >= 0 && ft.query(ends[i],i) == 0){
++ans;
ft.update(i,1);
}
cout << ans << " ";
}
output_run_time();
return 0;
}
Weierstrass
#include<bits/stdc++.h>
#define f_in(s) freopen(s,"r",stdin)
#define f_out(s) freopen(s,"w",stdout)
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll
#define rep(i,a,n) for(int i=(a),__##i=(n);i<=__##i;++i)
#define repe(i,a,n) for(int i=(a),__##i=(n);i<__##i;++i)
#define repv(i,n,a) for(int i=(n),__##i=(a);i>=__##i;--i)
#define repl(i,a,n) for(ll i=(a),__##i=(n);i<=__##i;++i)
#define lowbit(x) ((x)&-(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define mcpy(x,y) memcpy(x,y,sizeof(x))
#define popcount __builtin_popcount
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<db,db>
#define X first
#define Y second
#define LL __int128
#define ll long long
#define ull unsigned long long
#define db double
using namespace std;
mt19937_64 rndGen(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l,r) uniform_int_distribution<int>(l,r)(rndGen)
#define rll(l,r) uniform_int_distribution<ll>(l,r)(rndGen)
#define rreal(l,r) uniform_real_distribution<double>(l,r)(rndGen)
// #define HDU
inline ll read(){
#ifdef HDU
ll ret; scanf("%lld",&ret);
return ret;
#else
ll s=0,f=1; char c=getchar();
while(c<'0'||c>'9') f*=c=='-'?-1:1,c=getchar();
while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
return s*f;
#endif
}
template<class T> inline void cmax(T &a,T b){ a=max(a,b); }
template<class T> inline void cmin(T &a,T b){ a=min(a,b); }
const ll P=998244353;
inline ll pw(ll a,ll x=P-2){
ll ret=1;
for(;x;x>>=1,a=a*a%P) if(x&1) ret=ret*a%P;
return ret;
}
struct BIT{
int n;
vector<ll> c;
BIT(int n):n(n),c(n){}
void add(int x,ll v){
while(x<n) c[x]+=v,x+=lowbit(x);
}
ll sum(int x){
ll ret=0;
while(x) ret+=c[x],x-=lowbit(x);
return ret;
}
};
inline void wk(){
ll a=read(),b=read(),mb=(1<<__lg(b))*2;
ll ans=infl;
repe(i,b,mb){
if(a>i) continue;
ll ma=a;
while((ma&i)!=ma) ma+=lowbit(ma);
cmin(ans,ma-a+(ma!=b)+i-b);
}
printf("%lld\n",ans);
}
int main(){
repe(_,0,read()) wk();
return 0;
}
Kawaii
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t, n, m, k, a, b, mod = (1 << 20);
string s;
mt19937_64 rng;
int mul(int x, int y){
if(y == 0) return 1;
int ans = mul(x, y / 2);
if(y % 2 == 0) return (ans * ans) % mod;
else return (((ans * ans) % mod) * x) % mod;
}
void solve(){
int ans = b - a;
int A = a;
while(A <= b){
int q = (A | b);
if(q <= b) ans = min(ans, A - a + 1 + b - q);
A++;
}
int B = b, o = 1;
while(o < b) o = o * 2 + 1;
while(B <= o){
int q = (a | B);
if(q == B) ans = min(ans, B - b + 1);
B++;
}
cout << ans << "\n";
}
signed main(){
ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
rng.seed((int)main ^ time(0));
#ifdef Kawaii
auto starttime = chrono::high_resolution_clock::now();
#endif
cin >> t;
while(t--){
cin >> a >> b;
solve();
}
#ifdef Kawaii
auto endtime = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count();
cout << "\n=====" << "\nUsed: " << duration << " ms\n";
#endif
}
matouzouken
#include<bits/stdc++.h>
#define lp long long
#define ulp unsigned long long
#define pa pair < lp , lp >
#define fi first
#define se second
#define mp make_pair
#define ls x<<1
#define rs x<<1|1
#define kp push_back
#define db double
#define itn insert
#define pc putchar
#define rep(i,x,y) for(lp i=(x);i<=(y);i++)
#define per(i,x,y) for(lp i=(x);i>=(y);i--)
using namespace std;
inline lp read(){
lp r=0,f=0;char c=getchar();
while(!isdigit(c))f=c=='-',c=getchar();
while(isdigit(c))r=r*10+(c^48),c=getchar();
return f?-r:r;
}
inline lp minn(lp a,lp b){return a<b?a:b;}
inline lp maxx(lp a,lp b){return a>b?a:b;}
//inline lp sqt(lp x){lp res=sqrt(x)+1;while(res*res>x)res--;return res;}
lp gcd(lp a,lp b){return !b?a:gcd(b,a%b);}
lp lcm(lp a,lp b){return a/gcd(a,b)*b;}
void wr(lp x){if(x<0)x=-x,pc('-');if(x>9)wr(x/10);pc(x%10+'0');}
const lp ml=1e6+101;
const lp inf=1e15;
//const lp mk=+101;
//const lp mo=1e9+7;
//const lp mo=998244353;
lp t,n,m,q;
lp ans;
lp x[ml],ins[ml];
//pa a[ml];
char s[ml];
//string s;
//vector < lp > e[ml];
//map < lp , lp > atl;
//multiset < lp > s;
//---------------------------------------------------------------------------------------------------
//lp qpow(lp x,lp y=mo-2){lp res=1;while(y){if(y&1)res=res*x%mo;x=x*x%mo;y>>=1;}return res;}
/*
lp fac[ml],inv[ml];
void init_C(lp l){
fac[0]=inv[0]=1;
for(lp i=1;i<=l;i++)fac[i]=fac[i-1]*i%mo;
inv[l]=qpow(fac[l]);
for(lp i=l-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mo;
}
lp C(lp a,lp b){
if(a<0||b<0||a<b)return 0;
return fac[a]*inv[b]%mo*inv[a-b]%mo;
}
*/
//---------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------
/*
struct BIT{
lp sz[ml];
lp query(lp x){lp res=0;for(;x>=1;x-=x&-x)res+=sz[x];return res;}
void modify(lp x,lp y=1){for(;x<=n;x+=x&-x)sz[x]+=y;}
}str;
*/
//----------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------
/*
-----------------------------------------------------------------------------------
鍔ㄦ€佸紑鐐?鍖洪棿淇敼&鏈€灏忓€?灏佽 鏉庤秴绾挎鏍?
auther:wuxingzhi
浣跨敤鍓嶏細init(鍊煎煙)锛屾敼ML
鍑芥暟锛歁odify,Query,init
Ps:姹傛渶澶у€肩洿鎺ユ妸涓変釜">"鏀规垚"<"锛屾妸鈥渞eturn inf"鏀规垚"return -inf"锛屾妸"minn"鏀规垚"maxx"
-----------------------------------------------------------------------------------
*/
/*
struct Lc{
#define lo lson[x]
#define ro rson[x]
static const lp ML=1e6+101;
const lp inf=1e15;
lp N,tot;
lp lson[ML<<2],rson[ML<<2],k[ML<<2],b[ML<<2],vis[ML<<2];
lp calc(lp x,lp k,lp b){return x*k+b;}
void init(lp Num){N=Num;for(lp i=1;i<=tot;i++)lson[i]=rson[i]=k[i]=b[i]=vis[i]=0;tot=1;}
lp modify(lp qk,lp qb,lp ql,lp qr,lp x,lp l,lp r){
if(!x)x=++tot;
lp mid=(l+r)>>1;
if(ql<=l&&qr>=r){
if(!vis[x]){vis[x]=1,k[x]=qk,b[x]=qb;return x;}
if(calc(mid,k[x],b[x])>calc(mid,qk,qb))swap(qk,k[x]),swap(qb,b[x]);
if(calc(l,k[x],b[x])>calc(l,qk,qb))lo=modify(qk,qb,ql,qr,lo,l,mid);
if(calc(r,k[x],b[x])>calc(r,qk,qb))ro=modify(qk,qb,ql,qr,ro,mid+1,r);
return x;
}
if(ql<=mid)lo=modify(qk,qb,ql,qr,lo,l,mid);
if(qr>mid)ro=modify(qk,qb,ql,qr,ro,mid+1,r);
return x;
}
lp query(lp d,lp x,lp l,lp r){
if(!vis[x]||!x)return inf;
lp res=calc(d,k[x],b[x]),mid=(l+r)>>1;
if(l==r)return res;
if(d<=mid)return minn(res,query(d,lo,l,mid));
else return minn(res,query(d,ro,mid+1,r));
}
void Modify(lp k,lp b,lp l=-1,lp r=-1){l==-1?modify(k,b,0,N,1,0,N):modify(k,b,l,r,1,0,N);}
lp Query(lp d){return query(d,1,0,N);}
#undef lo
#undef ro
}t;
*/
//-----------------------------------------------------------------------------------------------------------
int main(){
cin>>t;
while(t--){
cin>>n>>m;
if(n>=m)cout<<n-m<<'\n';
else{
ans=m-n;
for(lp i=n;i<=m;i++)if(((i^m)&i)==0){ans=minn(ans,i-n+1);break;}
for(lp i=m;i;i++)if(((n^i)&n)==0){ans=minn(ans,i-m+1);break;}
cout<<ans<<'\n';
}
}
return 0;
}
Winterfrost
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<random>
#include<chrono>
#include<deque>
#include<cassert>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define mp std::make_pair
#define ulf Useful_little_function
#define abs ccf
#define inline __attribute__((always_inline))inline
#define INF (0x3f3f3f3f)
#define INT_INF (2147483647)
#define LLINF (0x3f3f3f3f3f3f3f3fll)
#define LL_INF (9223372036854775807)
#define memset __builtin_memset
#define popcount __builtin_popcount
std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
typedef long long ll;
typedef std::pair<int,int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
inline void file(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
namespace IO{
#define BUF_SIZE (1<<16)
#define OUT_SIZE (1<<16)
bool IOerror=0;
inline char nc(){static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;if(p1==pend){p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);if(pend==p1)return IOerror=1,-1;}return *p1++;}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline void read(int &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
inline void read(ll &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
inline void read(double &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;}
inline void read(char *s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;}
inline void read(char &c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return;}}
struct Ostream_fwrite{
char *buf,*p1,*pend;
Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
inline void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;}
inline void print(int x){static char s[15],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
inline void println(int x){print(x);out('\n');}
inline void print(ll x){static char s[25],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
inline void println(ll x){print(x);out('\n');}
inline void print(double x,int y){//y<18
static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
if(x<-1e-12)out('-'),x=-x;x*=mul[y];ll x1=(ll)floor(x);if(x-floor(x)>=0.5)++x1;ll x2=x1/mul[y],x3=x1-x2*mul[y];print(x2);if(y>0){out('.');for(size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i);print(x3);}
}
inline void println(double x,int y){print(x,y);out('\n');}
inline void print(char *s){while(*s)out(*s++);}
inline void println(char *s){while(*s)out(*s++);out('\n');}
inline void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
~Ostream_fwrite(){flush();}
}Ostream;
inline void print(int x){Ostream.print(x);}
inline void println(int x){Ostream.println(x);}
inline void print(char x){Ostream.out(x);}
inline void println(char x){Ostream.out(x);Ostream.out('\n');}
inline void print(ll x){Ostream.print(x);}
inline void println(ll x){Ostream.println(x);}
inline void print(double x,int y){Ostream.print(x,y);}
inline void println(double x,int y){Ostream.println(x,y);}
inline void print(char *s){Ostream.print(s);}
inline void println(char *s){Ostream.println(s);}
inline void println(){Ostream.out('\n');}
inline void flush(){Ostream.flush();}
#undef OUT_SIZE
#undef BUF_SIZE
}using namespace IO;
namespace Little_function{
inline int abs(int x){return x<0?-x:x;}
inline ll abs(ll x){return x<0?-x:x;}
inline double abs(double x){return x<0?-x:x;}
inline int max(const int &a,const int &b){return a>b?a:b;}
inline ll max(const ll &a,const ll &b){return a>b?a:b;}
inline double max(const double &a,const double &b){return a>b?a:b;}
inline int min(const int &a,const int &b){return a<b?a:b;}
inline ll min(const ll &a,const ll &b){return a<b?a:b;}
inline double min(const double &a,const double &b){return a<b?a:b;}
inline void swap(int &x,int &y){x^=y^=x^=y;}
inline void swap(ll &x,ll &y){x^=y^=x^=y;}
inline void swap(double &x,double &y){double t=x;x=y,y=t;}
inline int madd(const int &a,const int &b,const int &p){return (a+b)%p;}
inline int mdel(const int &a,const int &b,const int &p){return (a-b<0?a-b+p:a-b);}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
}using namespace Little_function;
int main(){int T;read(T);while(T--){
int a,b;read(a),read(b);
int ans=b-a;
for(int i=0;i<b-a;++i){
bool flag=0;int x=0;
for(int j=19;j>=0;--j){
int c=(((a+i)>>j)&1);
int d=((b>>j)&1);
if(c){
x|=(1<<j);
if(!d&&!flag) flag=1;
}
else if(!flag&&d) x|=(1<<j);
}
ans=min(ans,i+1+x-b);
}
println(ans);
}
return 0;
}
876pol
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pll pair<long long, long long>
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define vpll vector<pair<long long, long long>>
#define vec vector
#define indexed_set \
tree<long long, null_type, less<long long>, rb_tree_tag, \
tree_order_statistics_node_update>
#define FOR(i, s, e) for (long long i = s; i < e; i++)
#define CFOR(i, s, e) for (long long i = s; i <= e; i++)
#define RFOR(i, e, s) for (long long i = e - 1; i >= s; i--)
#define TRAV(a, c) for (auto a : c)
#define ITER(it, cs, ce) for (auto it = cs; it != ce; it++)
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl
mt19937_64 rng(100);
template <class T>
string to_string(vector<T> &vec) {
std::ostringstream vts;
if (!vec.empty()) {
std::copy(vec.begin(), vec.end() - 1,
std::ostream_iterator<T>(vts, ", "));
vts << vec.back();
}
return "[" + vts.str() + "]";
}
#define MOD 1000000007
#define FASTIO ;
#define PRECISION ;
//#define FILE ;
//#define SINGLE ;
#define MULTIPLE ;
//#define GOOGLE ;
void solve() {
ll a, b;
cin >> a >> b;
if (a == b) {
cout << "0\n";
return;
}
if ((a | b) == b) {
cout << "1\n";
return;
}
ll ans = b - a;
CFOR(i, 0, b - a) {
if (((a + i) | b) == b) {
ans = min(ans, i + 1);
break;
}
}
FOR(i, 0, 1000000) {
if ((a | (b + i)) == (b + i)) {
ans = min(ans, i + 1);
break;
}
}
cout << ans << "\n";
// if (a == b) {
// cout << "0\n";
// return;
// }
// if ((a | b) == b) {
// cout << "1\n";
// return;
// }
// ll ans = LLONG_MAX;
// RFOR(i, 30, 0) {
// if ((a & (1ll << i)) && !(b & (1ll << i))) {
// ll na = 0;
// ll nb = 0;
// RFOR(j, i + 1, 0) {
// if (a & (1ll << j)) {
// na |= (1ll << j);
// }
// if (b & (1ll << j)) {
// nb |= (1ll << j);
// }
// }
// cerr << na << " " << nb << "\n";
// ans = min(ans, na - nb + 1);
// break;
// }
// if (!(a & (1ll << i)) && (b & (1ll << i))) {
// if ((1ll << i) == b) {
// ans = min(ans, (1ll << i) - a);
// } else {
// ans = min(ans, (1ll << i) - a + 1);
// }
// }
// }
// cout << ans << "\n";
}
int main() {
#ifdef FASTIO
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#endif
#ifdef PRECISION
cout << fixed << setprecision(10);
#endif
#ifdef FILE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
#ifdef SINGLE
solve();
#endif
#ifdef MULTIPLE
int t;
cin >> t;
for (int i = 1; i <= t; i++) {
solve();
}
#endif
#ifdef GOOGLE
int t;
cin >> t;
for (int i = 1; i <= t; i++) {
cout << "Case #" << i << ": ";
solve();
}
#endif
}
xiaoququsd
#define A3F 0x7f7f7f7f,
#define A3E 0x7f7f7f7f;
#define A3D main(void)
#define A3C ++tmpans;
#define A3B namespace
#define A3A min(ans,
#define A39 min(ret,
#define A38 tmpans);
#define A37 tmpans
#define A36 endl;
#define A35 (T--)
#define A34 using
#define A33 while
#define A32 (((t
#define A31 (int
#define A30 (ret
#define A2F cout
#define A2E ++i)
#define A2D --k)
#define A2C else
#define A2B k));
#define A2A std;
#define A29 ans
#define A28 b);
#define A27 20;
#define A26 cin
#define A25 for
#define A24 int
#define A23 ret
#define A22 k);
#define A21 a)
#define A20 a,
#define A1F ==
#define A1E b)
#define A1D b;
#define A1C a;
#define A1B !=
#define A1A i;
#define A19 if
#define A18 (1
#define A17 (i
#define A16 k)
#define A15 (t
#define A14 +=
#define A13 0)
#define A12 0;
#define A11 1)
#define A10 <<
#define AF <=
#define AE >=
#define AD >>
#define AC T,
#define AB T;
#define AA +
#define A9 a
#define A8 k
#define A7 &
#define A6 t
#define A5 =
#define A4 i
#define A3 b
#define A2 -
#define A1 {
#define A0 }
#include <bits/stdc++.h>
#define A40 A34 A3B A2A A24 A3D A1 A24 AC A29 A5
#define A41 A3E A26 AD AB A33 A35 A1 A24 A20 A1D
#define A42 A26 AD A9 AD A1D A29 A5 A3 A2 A1C
#define A43 A25 A31 A4 A5 A1C A4 AF A1D A2E A1
#define A44 A24 A23 A5 A3F A6 A5 A1A A25 A31 A8
#define A45 A5 A27 A8 AE A12 A2D A1 A19 A32 AD
#define A46 A16 A7 A11 A1F A13 A1 A19 A15 AA A18
#define A47 A10 A16 AE A1E A1 A23 A5 A39 A6 AA
#define A48 A18 A10 A2B A0 A2C A1 A6 A14 A18 A10
#define A49 A22 A0 A0 A0 A24 A37 A5 A17 A2 A21
#define A4A AA A30 A2 A28 A19 A17 A1B A1E A3C A29
#define A4B A5 A3A A38 A0 A2F A10 A29 A10 A36 A0
#define A4C A0
#define A4D A40 A41 A42 A43 A44 A45 A46 A47 A48 A49
#define A4E A4A A4B A4C
#define A4F A4D A4E
#define A50(__FOX__) __FOX__
A50(A4F)
dimss
#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Size(a) (int)a.size()
#define ll long long
#define ld long double
// #define int long long
using namespace std;
void solve() {
int a, b;
cin >> a >> b;
if ((a | b) == b) {
cout << "1\n";
return;
}
int ans = b - a;
for (int k = b; k <= 2 * b + 100; k++) {
int val = k - b + 1;
if ((a | k) != k) {
int cur = 1e9;
for (int i = 21; i >= 0; i--) {
if (((a >> i) & 1) == 0 && ((k >> i) & 1))
cur = min(cur, (1 << i) - (a & (1 << (i)) - 1));
if (((a >> i) & 1) && !((k >> i) & 1)) {
// j = i;
break;
}
}
val += cur;
// assert(j != -1);
// val -= (a & ((1 << (j + 1)) - 1));
// while (((k >> j) & 1) == 0)
// j++;
// val += (1 << j);
}
ans = min(ans, val);
}
cout << ans << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef DIMSS
freopen("test.txt", "r", stdin);
#endif
int T = 1;
cin >> T;
while (T--) {
solve();
#ifdef DIMSS
cerr << "--------\n";
#endif
}
return 0;
}
Kanheyalal
#include<bits/stdc++.h>
using namespace std;
#define Jay_JAGANATH ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long
#define lld long long double
#define sz(a) int((a).size())
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define INF 1e18
ll mod = 1e9+7;
ll MOD = 998244353;
vector<int> v;
void solve() {
int a, b;
cin >> a >> b;
int ans = b - a;
int x = a;
while(x <= b) {
int t = x | b;
int c = x - a + 1 + t - b;
ans = min(ans, c);
x++;
}
x = b;
int lim = b + b - a;
while(x <= lim) {
int t = x | a;
int c = x - b + 1 + t - x;
ans = min(c, ans);
x++;
}
cout << ans << endl;
}
int32_t main() {
Jay_JAGANATH;
cout.tie(NULL);
int t=1;
cin >> t;
for(int i=0;i<31;i++) {
v.pb(pow(2, i));
}
while(t--) {
solve();
}
#ifndef ONLINE_JUDGE
cerr << "\nTime: " << (float)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#endif
}
/*
*/
Submissions of all the users for Problem D.
Weierstrass
#include<bits/stdc++.h>
#define f_in(s) freopen(s,"r",stdin)
#define f_out(s) freopen(s,"w",stdout)
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll
#define rep(i,a,n) for(int i=(a),__##i=(n);i<=__##i;++i)
#define repe(i,a,n) for(int i=(a),__##i=(n);i<__##i;++i)
#define repv(i,n,a) for(int i=(n),__##i=(a);i>=__##i;--i)
#define repl(i,a,n) for(ll i=(a),__##i=(n);i<=__##i;++i)
#define lowbit(x) ((x)&-(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define mcpy(x,y) memcpy(x,y,sizeof(x))
#define popcount __builtin_popcount
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<db,db>
#define X first
#define Y second
#define LL __int128
#define ll long long
#define ull unsigned long long
#define db double
using namespace std;
mt19937_64 rndGen(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l,r) uniform_int_distribution<int>(l,r)(rndGen)
#define rll(l,r) uniform_int_distribution<ll>(l,r)(rndGen)
#define rreal(l,r) uniform_real_distribution<double>(l,r)(rndGen)
// #define HDU
inline ll read(){
#ifdef HDU
ll ret; scanf("%lld",&ret);
return ret;
#else
ll s=0,f=1; char c=getchar();
while(c<'0'||c>'9') f*=c=='-'?-1:1,c=getchar();
while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
return s*f;
#endif
}
template<class T> inline void cmax(T &a,T b){ a=max(a,b); }
template<class T> inline void cmin(T &a,T b){ a=min(a,b); }
const ll P=998244353;
inline ll pw(ll a,ll x=P-2){
ll ret=1;
for(;x;x>>=1,a=a*a%P) if(x&1) ret=ret*a%P;
return ret;
}
struct BIT{
int n;
vector<ll> c;
BIT(int n):n(n),c(n){}
void add(int x,ll v){
while(x<n) c[x]+=v,x+=lowbit(x);
}
ll sum(int x){
ll ret=0;
while(x) ret+=c[x],x-=lowbit(x);
return ret;
}
};
inline void wk(){
int n=read();
vector<ll> a(n);
repe(i,0,n) a[i]=read();
vector<int> ans(n);
vector<vector<ll>> st(20,vector<ll>(n));
repe(i,0,n) st[0][i]=a[i];
repe(s,0,19) repe(i,0,n-(1<<s)){
st[s+1][i]=__gcd(st[s][i],st[s][i+(1<<s)]);
}
auto gcd=[&](int l,int r){
int d=__lg(r-l+1);
return __gcd(st[d][l],st[d][r-(1<<d)+1]);
};
vector<int> idx(n+1);
iota(idx.begin(),idx.end(),0);
int l=0;
repe(r,0,n){
if(a[r]==1){
ans[r]=1,l=r+1;
continue;
}
int x=*lower_bound(idx.begin(),idx.begin()+r,0,[&](int i,int _){
return gcd(i,r)<r-i+1;
});
if(x<l) continue;
if(gcd(x,r)==r-x+1) ans[r]=1,l=r+1;
}
repe(i,1,n) ans[i]+=ans[i-1];
repe(i,0,n) printf("%d ",ans[i]);
}
int main(){
repe(_,0,1) wk();
return 0;
}
codebuster_10
#include <bits/stdc++.h>
#define int int64_t //be careful about this
using namespace std;
namespace IN{
template<class T> void read(vector<T> &A);
template<class S,class T> void read(pair<S,T> &A);
template<class T,size_t N> void read(array<T,N> &A);
template<class T> void read(T& x){
cin >> x;}
template<class H, class... T> void read(H& h, T&... t){
read(h); read(t...);}
template<class T> void read(vector<T> &A){
for(auto& x : A) read(x);}
template<class S,class T> void read(pair<S,T> &A){
read(A.first); read(A.second);}
template<class T,size_t N> void read(array<T,N> &A){
for(int i = 0; i < N; ++i) read(A[i]);}
}
namespace OUT{
template<typename T>
void __p(T a) {
cout<<a;
}
template<typename T, typename F>
void __p(pair<T, F> a) {
cout<<"{";
__p(a.first);
cout<<",";
__p(a.second);
cout<<"}\n";
}
template<typename T, size_t N>
void __p(array<T,N> a){
cout<<"{";
for(int i = 0; i < N; ++i)
__p(a[i]),cout<<",}\n"[i+1==N];
}
template<typename T>
void __p(std::vector<T> a) {
cout<<"{";
for(auto it=a.begin(); it<a.end(); it++)
__p(*it),cout<<",}\n"[it+1==a.end()];
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
__p(a1);
__p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
cout<<name<<" : ";
__p(arg1);
cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
int bracket=0,i=0;
for(;; i++)
if(names[i]==','&&bracket==0)
break;
else if(names[i]=='(')
bracket++;
else if(names[i]==')')
bracket--;
const char *comma=names+i;
cout.write(names,comma-names)<<" : ";
__p(arg1);
cout<<" | ";
__f(comma+1,args...);
}
#define trace(...) cout<<"Line:"<<__LINE__<<" ", __f(#__VA_ARGS__, __VA_ARGS__)
}
namespace FUN{
void IO(string s = ""){
ios_base::sync_with_stdio(NULL);
cin.tie(nullptr);
cout.precision(20);
cout << fixed;
if(!s.empty()){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
const auto start_time = chrono::high_resolution_clock::now();
void output_run_time(){
// will work for ac,cc&&cf.
#ifndef ONLINE_JUDGE
auto end_time = chrono::high_resolution_clock::now();
chrono::duration<double> diff = end_time-start_time;
cout << "\n\n\nTime Taken : " << diff.count();
#endif
}
template<class T> bool ckmin(T& a, const T b) { return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T b) { return a < b ? a = b, 1 : 0;}
}
using namespace IN;
using namespace OUT;
using namespace FUN;
template<class T>
struct basic_segment_tree {
const T ID = 0;
T comb(T a, T b){// comb(ID,b) = b
return __gcd(a,b);
}
int n; vector<T> seg;
void init(int _n){
n = _n; seg.assign(2 * n,ID);
}
void pull(int p){
seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
}
void upd(int p, T val){ // update val at position p
seg[p += n] = val;
for(p /= 2; p; p /= 2) pull(p);
}
T query(int l, int r){ // query on interval [l, r]
T ra = ID, rb = ID;
for(l += n, r += n+1; l < r; l /= 2, r /= 2){
if(l&1) ra = comb(ra,seg[l++]);
if(r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
template<typename T>
struct fenwick_tree{
int tree_n = 0;
T tree_sum = 0;
vector<T> tree;
fenwick_tree(int n = -1){
if(n >= 0)
init(n);
}
static int highest_bit(int x){
return x == 0 ? -1 : 31 - __builtin_clz(x);
}
void init(int n) {
tree_n = n;
tree_sum = 0;
tree.assign(tree_n + 1, 0);
}
// O(n) initialization of the Fenwick tree.
template<typename T_array>
void build(const T_array &initial){
assert(int(initial.size()) == tree_n);
tree_sum = 0;
for(int i = 1; i <= tree_n; i++){
tree[i] = initial[i-1];
tree_sum += initial[i-1];
for(int k = (i & -i) >> 1; k > 0; k >>= 1)
tree[i] += tree[i - k];
}
}
// index is in [0, tree_n).
void update(int index, const T &change){
assert(0 <= index && index < tree_n);
tree_sum += change;
for(int i = index + 1; i <= tree_n; i += i & -i)
tree[i] += change;
}
// Returns the sum of the range [0, count).
T query(int count) const {
count = min(count, tree_n);
T sum = 0;
for(int i = count; i > 0; i -= i & -i)
sum += tree[i];
return sum;
}
// Returns the sum of the range [start, tree_n).
T query_suffix(int start) const {
return tree_sum - query(start);
}
// Returns the sum of the range [a, b).
T query(int a, int b) const {
return query(b) - query(a);
}
// Returns the element at index a in O(1) amortized across every index. Equivalent to query(a, a + 1).
T get(int a) const {
assert(0 <= a && a < tree_n);
int above = a + 1;
T sum = tree[above];
above -= above & -above;
while (a != above){
sum -= tree[a];
a -= a & -a;
}
return sum;
}
bool set(int index, T value){
assert(0 <= index && index < tree_n);
T current = get(index);
if(current == value)
return false;
update(index, value - current);
return true;
}
// Returns the largest p in `[0, tree_n]` such that `query(p) <= sum`. Returns -1 if no such p exists (`sum < 0`).
// Can be used as an ordered set/multiset on indices in `[0, tree_n)` by using the tree as a 0/1 or frequency array:
// `set(index, 1)` is equivalent to insert(index). `update(index, +1)` is equivalent to multiset.insert(index).
// `set(index, 0)` or `update(index, -1)` are equivalent to erase(index).
// `get(index)` provides whether index is present or not, or the count of index (if multiset).
// `query(index)` provides the count of elements < index.
// `find_last_prefix(k)` finds the k-th smallest element (0-indexed). Returns `tree_n` for `sum >= set.size()`.
int find_last_prefix(T sum) const {
if(sum < 0)
return -1;
int prefix = 0;
for(int k = highest_bit(tree_n); k >= 0; k--)
if(prefix + (1 << k) <= tree_n && tree[prefix + (1 << k)] <= sum){
prefix += 1 << k;
sum -= tree[prefix];
}
return prefix;
}
};
signed main(){
IO();
int n;
read(n);
vector<int> a(n);
read(a);
basic_segment_tree<int> st;
st.init(n);
for(int i = 0; i < n; ++i)
st.upd(i,a[i]);
vector<int> ends(n,-1);
for(int i = 0; i < n; ++i){
int lo = i, hi = n;
while(hi - lo > 1){
int mid = (hi + lo)/2;
st.query(i,mid) - (mid - i + 1) >= 0 ? lo = mid : hi = mid;
}
if(st.query(i,lo) == (lo - i + 1))
ends[lo] = i;
}
fenwick_tree<int> ft;
ft.init(n);
int ans = 0;
for(int i = 0; i < n; ++i){
if(ends[i] >= 0 && ft.query(ends[i],i) == 0){
++ans;
ft.update(i,1);
}
cout << ans << " ";
}
output_run_time();
return 0;
}
876pol
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pll pair<long long, long long>
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define vpll vector<pair<long long, long long>>
#define vec vector
#define indexed_set \
tree<long long, null_type, less<long long>, rb_tree_tag, \
tree_order_statistics_node_update>
#define FOR(i, s, e) for (long long i = s; i < e; i++)
#define CFOR(i, s, e) for (long long i = s; i <= e; i++)
#define RFOR(i, e, s) for (long long i = e - 1; i >= s; i--)
#define TRAV(a, c) for (auto a : c)
#define ITER(it, cs, ce) for (auto it = cs; it != ce; it++)
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl
mt19937_64 rng(100);
template <class T>
string to_string(vector<T> &vec) {
std::ostringstream vts;
if (!vec.empty()) {
std::copy(vec.begin(), vec.end() - 1,
std::ostream_iterator<T>(vts, ", "));
vts << vec.back();
}
return "[" + vts.str() + "]";
}
#define MOD 1000000007
#define FASTIO ;
#define PRECISION ;
//#define FILE ;
#define SINGLE ;
//#define MULTIPLE ;
//#define GOOGLE ;
ll gcd(ll a, ll b) { return ((b == 0) ? a : gcd(b, a % b)); }
struct sparse_table {
vector<vector<ll>> table;
sparse_table(vector<ll> a) {
ll n = a.size() + 1;
ll h = ceil(log2(n));
table = vector<vector<ll>>(h, vector<ll>(n));
for (ll i = 0; i < n; i++) table[0][i] = a[i];
for (ll i = 1; i < h; i++) {
for (ll j = 0; j + (1 << i) <= n; j++) {
table[i][j] =
gcd(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
}
}
ll query(ll l, ll r) {
r++;
ll p = 31 - __builtin_clz(r - l);
return gcd(table[p][l], table[p][r - (1 << p)]);
}
};
void solve() {
ll n;
cin >> n;
vll a(n);
FOR(i, 0, n) cin >> a[i];
sparse_table st(a);
ll l = 0;
ll curr = 0;
FOR(r, 0, n) {
while (st.query(l, r) < r - l + 1) l++;
if (st.query(l, r) == r - l + 1) {
curr++;
l = r + 1;
}
cout << curr << " ";
}
cout << "\n";
}
int main() {
#ifdef FASTIO
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#endif
#ifdef PRECISION
cout << fixed << setprecision(10);
#endif
#ifdef FILE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
#ifdef SINGLE
solve();
#endif
#ifdef MULTIPLE
int t;
cin >> t;
for (int i = 1; i <= t; i++) {
solve();
}
#endif
#ifdef GOOGLE
int t;
cin >> t;
for (int i = 1; i <= t; i++) {
cout << "Case #" << i << ": ";
solve();
}
#endif
}
Winterfrost
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<random>
#include<chrono>
#include<deque>
#include<cassert>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define mp std::make_pair
#define ulf Useful_little_function
#define abs ccf
#define inline __attribute__((always_inline))inline
#define INF (0x3f3f3f3f)
#define INT_INF (2147483647)
#define LLINF (0x3f3f3f3f3f3f3f3fll)
#define LL_INF (9223372036854775807)
#define memset __builtin_memset
#define popcount __builtin_popcount
std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
typedef long long ll;
typedef std::pair<int,int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
inline void file(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
namespace IO{
#define BUF_SIZE (1<<16)
#define OUT_SIZE (1<<16)
bool IOerror=0;
inline char nc(){static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;if(p1==pend){p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);if(pend==p1)return IOerror=1,-1;}return *p1++;}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline void read(int &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
inline void read(ll &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
inline void read(double &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;}
inline void read(char *s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;}
inline void read(char &c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return;}}
struct Ostream_fwrite{
char *buf,*p1,*pend;
Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
inline void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;}
inline void print(int x){static char s[15],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
inline void println(int x){print(x);out('\n');}
inline void print(ll x){static char s[25],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
inline void println(ll x){print(x);out('\n');}
inline void print(double x,int y){//y<18
static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
if(x<-1e-12)out('-'),x=-x;x*=mul[y];ll x1=(ll)floor(x);if(x-floor(x)>=0.5)++x1;ll x2=x1/mul[y],x3=x1-x2*mul[y];print(x2);if(y>0){out('.');for(size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i);print(x3);}
}
inline void println(double x,int y){print(x,y);out('\n');}
inline void print(char *s){while(*s)out(*s++);}
inline void println(char *s){while(*s)out(*s++);out('\n');}
inline void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
~Ostream_fwrite(){flush();}
}Ostream;
inline void print(int x){Ostream.print(x);}
inline void println(int x){Ostream.println(x);}
inline void print(char x){Ostream.out(x);}
inline void println(char x){Ostream.out(x);Ostream.out('\n');}
inline void print(ll x){Ostream.print(x);}
inline void println(ll x){Ostream.println(x);}
inline void print(double x,int y){Ostream.print(x,y);}
inline void println(double x,int y){Ostream.println(x,y);}
inline void print(char *s){Ostream.print(s);}
inline void println(char *s){Ostream.println(s);}
inline void println(){Ostream.out('\n');}
inline void flush(){Ostream.flush();}
#undef OUT_SIZE
#undef BUF_SIZE
}using namespace IO;
namespace Little_function{
inline int abs(int x){return x<0?-x:x;}
inline ll abs(ll x){return x<0?-x:x;}
inline double abs(double x){return x<0?-x:x;}
inline int max(const int &a,const int &b){return a>b?a:b;}
inline ll max(const ll &a,const ll &b){return a>b?a:b;}
inline double max(const double &a,const double &b){return a>b?a:b;}
inline int min(const int &a,const int &b){return a<b?a:b;}
inline ll min(const ll &a,const ll &b){return a<b?a:b;}
inline double min(const double &a,const double &b){return a<b?a:b;}
inline void swap(int &x,int &y){x^=y^=x^=y;}
inline void swap(ll &x,ll &y){x^=y^=x^=y;}
inline void swap(double &x,double &y){double t=x;x=y,y=t;}
inline int madd(const int &a,const int &b,const int &p){return (a+b)%p;}
inline int mdel(const int &a,const int &b,const int &p){return (a-b<0?a-b+p:a-b);}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
}using namespace Little_function;
const int N=2e5+13;
struct Node{int val,l,r,nxt;}a[N];
int n,head,tot;
int main(){
read(n);int sum=0;
for(int i=1;i<=n;++i){
int x;read(x);
a[++tot]=(Node){x,i,i,head};head=tot;
for(int j=head;j;j=a[j].nxt) a[j].val=gcd(a[j].val,x);
for(int j=head;j&&a[j].nxt;j=a[j].nxt)
if(a[j].val==a[a[j].nxt].val) a[j].l=a[a[j].nxt].l,a[j].nxt=a[a[j].nxt].nxt;
for(int j=head,c=0;j;c+=a[j].r-a[j].l+1,j=a[j].nxt)
if(a[j].val>=c+1&&a[j].val<=c+a[j].r-a[j].l+1){++sum;head=0;break;}
print(sum),print(' ');
}
return 0;
}
xiaoququsd
#define A45 cout << ans << " ";
#define A44 __gcd(f[l][zz],
#define A43 f[500005][25];
#define A42 __gcd(f[j][i
#define A41 (func(best,
#define A40 (func(mid,
#define A3F a[500005],
#define A3E main(void)
#define A3D namespace
#define A3C 1][zz]);
#define A3B func(int
#define A3A f[j][i]
#define A39 f[i][0]
#define A38 ans++;
#define A37 __lg(r
#define A36 1))][i
#define A35 return
#define A34 a[i];
#define A33 using
#define A32 while
#define A31 ++j)
#define A30 last
#define A2F (int
#define A2E mid;
#define A2D ++i)
#define A2C best
#define A2B std;
#define A2A else
#define A29 1]);
#define A28 int
#define A27 20;
#define A26 1],
#define A25 mid
#define A24 ans
#define A23 f[j
#define A22 1);
#define A21 f[r
#define A20 for
#define A1F cin
#define A1E zz)
#define A1D 1)
#define A1C i)
#define A1B i,
#define A1A if
#define A19 1,
#define A18 l,
#define A17 l;
#define A16 1;
#define A15 <<
#define A14 <=
#define A13 ==
#define A12 n;
#define A11 >>
#define A10 r)
#define AF (1
#define AE (i
#define AD (l
#define AC 0,
#define AB zz
#define AA 0;
#define A9 r
#define A8 1
#define A7 -
#define A6 +
#define A5 =
#define A4 j
#define A3 l
#define A2 i
#define A1 {
#define A0 }
#include <bits/stdc++.h>
#define A46 A33 A3D A2B A28 A3F A43 A28 A3B A18 A28
#define A47 A10 A1 A28 AB A5 A37 A7 A3 A6 A22
#define A48 A35 A44 A21 A7 AF A15 A1E A6 A3C A0
#define A49 A28 A3E A1 A28 A12 A1F A11 A12 A20 A2F
#define A4A A2 A5 A16 A2 A14 A12 A2D A1 A1F A11
#define A4B A34 A0 A20 A2F A2 A5 A16 A2 A14 A12
#define A4C A2D A1 A39 A5 A34 A0 A20 A2F A2 A5
#define A4D A16 A2 A14 A27 A2D A1 A20 A2F A4 A5
#define A4E A16 A4 A6 AF A15 A1C A7 A8 A14 A12
#define A4F A31 A1 A3A A5 A42 A7 A26 A23 A6 AF
#define A50 A15 AE A7 A36 A7 A29 A0 A0 A28 A30
#define A51 A5 AC A24 A5 AA A20 A2F A2 A5 A16
#define A52 A2 A14 A12 A2D A1 A28 A3 A5 A30 A6
#define A53 A19 A9 A5 A1B A2C A5 A17 A32 AD A14
#define A54 A10 A1 A28 A25 A5 AD A6 A10 A11 A16
#define A55 A1A A40 A1C A14 A2 A7 A25 A6 A1D A1
#define A56 A3 A5 A25 A6 A19 A2C A5 A2E A0 A2A
#define A57 A1 A9 A5 A25 A7 A16 A0 A0 A1A A41
#define A58 A1C A13 A2 A7 A2C A6 A1D A1 A30 A5
#define A59 A1B A38 A0 A45 A0 A0
#define A5A A46 A47 A48 A49 A4A A4B A4C A4D A4E A4F
#define A5B A50 A51 A52 A53 A54 A55 A56 A57 A58 A59
#define A5C A5A A5B
#define A5D(__FOX__) __FOX__
A5D(A5C)
Kanheyalal
#include<bits/stdc++.h>
using namespace std;
#define Jay_JAGANATH ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long
#define lld long long double
#define sz(a) int((a).size())
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define INF 1e18
ll mod = 1e9+7;
ll MOD = 998244353;
template < typename T >
struct SparseTable {
vector<vector<T>> table;
vector<int> log;
int maxLog;
SparseTable(int n, vector<T> &arr) {
log.resize(n+1);
log[1] = 0;
for(int i=2;i<=n;i++) {
log[i] = 1 + log[i/2];
}
maxLog = log[n];
build(arr);
}
T combine(T &x, T &y) {
return __gcd(x, y);
}
void build(vector<T> &arr) {
int n = arr.size();
table.assign(n, vector<T>(25));
for(int l=n-1;l>=0;l--) {
for(int w=0;w<25;w++) {
int r = l + (1 << w) - 1;
if(r >= n) break;
if(w == 0) table[l][w] = arr[l];
else table[l][w] = combine(table[l][w-1], table[l + (1 << (w-1))][w-1]);
}
}
}
int queryIdempotent(int l, int r) {
int w = r - l;
int power = log[w];
return combine(table[l][power] , table[r - (1 << power)+1][power]);
}
};
void solve() {
int n;
cin >> n;
vector<int> arr(n);
for(int i=0;i<n;i++) {
cin >> arr[i];
}
SparseTable<int> sp(n, arr);
set<int> s;
int ans = 0;
for(int i=0;i<n;i++) {
if(arr[i] == 1) {
ans++;
s.insert(i);
cout << ans << " ";
continue;
}
int l = 0, r = i;
bool f = 0;
int ind = -1;
while(l <= r) {
int mid = (l + r) / 2;
int len = i - mid + 1;
int gcd = sp.queryIdempotent(mid, i);
if( gcd == len) {
f = 1;
ind = mid;
break;
}
if(gcd < len) {
l = mid + 1;
} else {
r = mid - 1;
}
}
if(f) {
auto it = s.lower_bound(ind);
if(it == s.end()) {
ans++;
s.insert(i);
}
}
cout << ans << " ";
}
cout << endl;
}
int32_t main() {
Jay_JAGANATH;
cout.tie(NULL);
int t=1;
// cin >> t;
while(t--) {
solve();
}
#ifndef ONLINE_JUDGE
cerr << "\nTime: " << (float)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#endif
}
/*
*/
dimss
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Size(a) (int)a.size()
#define ll long long
#define ld long double
// #define int long long
using namespace std;
const int N = 2e5 + 100;
int n;
int a[N];
int t[N * 4];
void build() {
for (int i = 0; i < n; i++)
t[i + n] = a[i];
for (int i = n - 1; i >= 1; i--)
t[i] = gcd(t[i << 1], t[(i << 1) | 1]);
}
int get(int l, int r) {
l += n;
r += n;
int res = 0;
while (l < r) {
if (l & 1) {
res = gcd(res, t[l]);
l++;
}
if (r & 1) {
r ^= 1;
res = gcd(res, t[r]);
}
l >>= 1;
r >>= 1;
}
return res;
}
void update(int i, int x) {
a[i] = x;
i += n;
t[i] = x;
i >>= 1;
while (i) {
t[i] = gcd(t[i << 1], t[(i << 1) | 1]);
i >>= 1;
}
}
void solve() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
build();
int ans = 0;
for (int i = 0; i < n; i++) {
int x = a[i];
int last = 1e9;
while (true) {
int l = -1, r = i;
while (l + 1 != r) {
int m = (l + r) / 2;
if (get(m, i + 1) >= x)
r = m;
else
l = m;
}
if (i - last + 1 < x && x <= i - r + 1) {
ans++;
update(i, 1);
break;
}
last = r;
if (r == 0)
break;
x = gcd(x, a[r - 1]);
}
cout << ans << " ";
}
cout << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef DIMSS
freopen("test.txt", "r", stdin);
#endif
int T = 1;
// cin >> T;
while (T--) {
solve();
#ifdef DIMSS
cerr << "--------\n";
#endif
}
return 0;
}
Kawaii
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t, n, m, k, a[1000005], mod = 1e9 + 7, Gcd[200005][20], ans[1000005], L[200005];
string s;
mt19937_64 rng;
int mul(int x, int y){
if(y == 0) return 1;
int ans = mul(x, y / 2);
if(y % 2 == 0) return (ans * ans) % mod;
else return (((ans * ans) % mod) * x) % mod;
}
int getgcd(int l, int r){
int p = L[r - l + 1];
return __gcd(Gcd[l][p], Gcd[r - (1 << p) + 1][p]);
}
void solve(){
for(int i = 2; i <= 2e5; i++) L[i] = L[i / 2] + 1;
for(int i = 1; i <= n; i++) Gcd[i][0] = a[i];
for(int i = 1; i <= 20; i++){
for(int j = 1; j + (1 << i - 1) <= n; j++){
Gcd[j][i] = __gcd(Gcd[j][i - 1], Gcd[j + (1 << i - 1)][i - 1]);
}
}
for(int i = 1; i <= n; i++){
int l = i, r = n + 1;
while(r - l > 1){
int mid = (l + r) / 2;
if(getgcd(i, mid) >= mid - i + 1) l = mid;
else r = mid;
}
if(getgcd(i, l) == l - i + 1){
ans[l]++, ans[n + 1]--;
i = l;
}
}
for(int i = 1; i <= n; i++) ans[i] += ans[i - 1];
for(int i = 1; i <= n; i++) cout << ans[i] <<" ";
}
signed main(){
ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
rng.seed((int)main ^ time(0));
#ifdef Kawaii
auto starttime = chrono::high_resolution_clock::now();
#endif
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
solve();
#ifdef Kawaii
auto endtime = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count();
cout << "\n=====" << "\nUsed: " << duration << " ms\n";
#endif
}
matouzouken
#include<bits/stdc++.h>
#define lp long long
#define ulp unsigned long long
#define pa pair < lp , lp >
#define fi first
#define se second
#define mp make_pair
#define ls x<<1
#define rs x<<1|1
#define kp push_back
#define db double
#define itn insert
#define pc putchar
#define rep(i,x,y) for(lp i=(x);i<=(y);i++)
#define per(i,x,y) for(lp i=(x);i>=(y);i--)
using namespace std;
inline lp read(){
lp r=0,f=0;char c=getchar();
while(!isdigit(c))f=c=='-',c=getchar();
while(isdigit(c))r=r*10+(c^48),c=getchar();
return f?-r:r;
}
inline lp minn(lp a,lp b){return a<b?a:b;}
inline lp maxx(lp a,lp b){return a>b?a:b;}
//inline lp sqt(lp x){lp res=sqrt(x)+1;while(res*res>x)res--;return res;}
lp gcd(lp a,lp b){return !b?a:gcd(b,a%b);}
lp lcm(lp a,lp b){return a/gcd(a,b)*b;}
void wr(lp x){if(x<0)x=-x,pc('-');if(x>9)wr(x/10);pc(x%10+'0');}
const lp ml=1e6+101;
const lp inf=1e15;
//const lp mk=+101;
//const lp mo=1e9+7;
//const lp mo=998244353;
lp t,n,m,q;
lp ans;
lp x[ml],ins[ml];
//pa a[ml];
//char s[ml];
//string s;
//vector < lp > e[ml];
//map < lp , lp > atl;
//multiset < lp > s;
//---------------------------------------------------------------------------------------------------
//lp qpow(lp x,lp y=mo-2){lp res=1;while(y){if(y&1)res=res*x%mo;x=x*x%mo;y>>=1;}return res;}
/*
lp fac[ml],inv[ml];
void init_C(lp l){
fac[0]=inv[0]=1;
for(lp i=1;i<=l;i++)fac[i]=fac[i-1]*i%mo;
inv[l]=qpow(fac[l]);
for(lp i=l-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mo;
}
lp C(lp a,lp b){
if(a<0||b<0||a<b)return 0;
return fac[a]*inv[b]%mo*inv[a-b]%mo;
}
*/
//---------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------
/*
struct BIT{
lp sz[ml];
lp query(lp x){lp res=0;for(;x>=1;x-=x&-x)res+=sz[x];return res;}
void modify(lp x,lp y=1){for(;x<=n;x+=x&-x)sz[x]+=y;}
}str;
*/
//----------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------
/*
-----------------------------------------------------------------------------------
鍔ㄦ€佸紑鐐?鍖洪棿淇敼&鏈€灏忓€?灏佽 鏉庤秴绾挎鏍?
auther:wuxingzhi
浣跨敤鍓嶏細init(鍊煎煙)锛屾敼ML
鍑芥暟锛歁odify,Query,init
Ps:姹傛渶澶у€肩洿鎺ユ妸涓変釜">"鏀规垚"<"锛屾妸鈥渞eturn inf"鏀规垚"return -inf"锛屾妸"minn"鏀规垚"maxx"
-----------------------------------------------------------------------------------
*/
/*
struct Lc{
#define lo lson[x]
#define ro rson[x]
static const lp ML=1e6+101;
const lp inf=1e15;
lp N,tot;
lp lson[ML<<2],rson[ML<<2],k[ML<<2],b[ML<<2],vis[ML<<2];
lp calc(lp x,lp k,lp b){return x*k+b;}
void init(lp Num){N=Num;for(lp i=1;i<=tot;i++)lson[i]=rson[i]=k[i]=b[i]=vis[i]=0;tot=1;}
lp modify(lp qk,lp qb,lp ql,lp qr,lp x,lp l,lp r){
if(!x)x=++tot;
lp mid=(l+r)>>1;
if(ql<=l&&qr>=r){
if(!vis[x]){vis[x]=1,k[x]=qk,b[x]=qb;return x;}
if(calc(mid,k[x],b[x])>calc(mid,qk,qb))swap(qk,k[x]),swap(qb,b[x]);
if(calc(l,k[x],b[x])>calc(l,qk,qb))lo=modify(qk,qb,ql,qr,lo,l,mid);
if(calc(r,k[x],b[x])>calc(r,qk,qb))ro=modify(qk,qb,ql,qr,ro,mid+1,r);
return x;
}
if(ql<=mid)lo=modify(qk,qb,ql,qr,lo,l,mid);
if(qr>mid)ro=modify(qk,qb,ql,qr,ro,mid+1,r);
return x;
}
lp query(lp d,lp x,lp l,lp r){
if(!vis[x]||!x)return inf;
lp res=calc(d,k[x],b[x]),mid=(l+r)>>1;
if(l==r)return res;
if(d<=mid)return minn(res,query(d,lo,l,mid));
else return minn(res,query(d,ro,mid+1,r));
}
void Modify(lp k,lp b,lp l=-1,lp r=-1){l==-1?modify(k,b,0,N,1,0,N):modify(k,b,l,r,1,0,N);}
lp Query(lp d){return query(d,1,0,N);}
#undef lo
#undef ro
}t;
*/
//-----------------------------------------------------------------------------------------------------------
const lp mk=22;
const lp L=21;
lp s[ml][mk];
lp get(lp l,lp r){
lp b=__lg(r-l+1);
return gcd(s[l][b],s[r-(1ll<<b)+1][b]);
}
void init(){
for(lp i=1;i<=n;i++)s[i][0]=x[i];
for(lp i=1;i<=L;i++)
for(lp j=1;j<=n-(1ll<<i)+1;j++)s[j][i]=gcd(s[j][i-1],s[j+(1ll<<(i-1))][i-1]);
}
int main(){
cin>>n;
for(lp i=1;i<=n;i++)x[i]=read();
init();
lp lst=0;
for(lp i=1;i<=n;i++){
lp l=lst+1,r=i,mid,res=-1;
while(l<=r){
mid=(l+r)>>1;
if(get(mid,i)-(i-mid+1)>=0)r=mid-1,res=mid;
else l=mid+1;
}
//cout<<endl<<" step inf "<<lst<<" "<<i<<" "<<res<<endl;
if((res==-1)||(get(res,i)!=i-res+1))cout<<ans<<" ";
else lst=i,ans++,cout<<ans<<" ";
}
return 0;
}
One can clearly see that none of the submissions in question are similar to one another. So I request MikeMirzayanov to please look into it.
