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.
UPD : I think their is a bug in plagiarism checker due to which it compared my submission with itself as it is written in the message "Attention! Your solution 144548751 for the problem 1632C significantly coincides with solutions Weierstrass/144543081, codebuster_10/ 144548751, .."
