Submission #1115856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115856		8pete8	XOR Sum (info1cup17_xorsum)	C++17	7 / 100	864 ms	131072 KiB

xorsum

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
//#define int long long
#define double long double
const int mxn=1e6+5,lg=29,inf=1e9,minf=-1e9;
int n;
void print(int x){
	for(int j=0;j<=3;j++){
		if(x&(1LL<<j))cout<<1;
		else cout<<0;
	}
	cout<<'\n';
}
void bruteforcecheck(){
	int x=1000;
	for(int k=0;k<lg;k++){
		vector<int>v;
		for(int i=0;i<10000;i++){
			int a=x+i;
			if((a&(1LL<<k)))v.pb(i);
		}
		int cnt=1,gap=0;
		for(int i=1;i<v.size();i++)if(v[i]-v[i-1]!=1){
			cnt++;
			if(gap&&gap!=v[i]-v[i-1])assert(0);
			gap=v[i]-v[i-1];
		}
		if(v.size()){
			cout<<cnt<<' '<<gap<<' '<<v[0]<<' '<<k<<'\n';
		}
	}
}
struct fen{
	int fwk[mxn+10];
	vector<int>keep;
	void update(int pos,int val){
		pos++;
		keep.pb(pos);
		for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val;
	}
	int qry(int pos){
		pos++;
		if(pos==0)return 0;
		int sum=0;
		for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
		return sum;
	}
	void re(){
		for(auto j:keep){
			for(int i=j;i<=n;i+=(i&-i))fwk[i]--;
		}
		keep.clear();
	}
}t;
int st[mxn+10][lg+2];
int between(int x,int l,int r){
	if(l<=r)return (l<=x&&x<=r);
	return (l<=x||x<=r);
}

int P[mxn+10],C[mxn+10];
int32_t main(){
	fastio
	cin>>n;
	vector<int>v(n);
	P[0]=1;
	for(int i=1;i<=lg;i++)P[i]=P[i-1]*2;
	for(int i=0;i<n;i++)cin>>v[i];
	sort(all(v));
	for(int i=0;i<n;i++){
		for(int j=0;j<=lg;j++)st[i][j]=inf;
		for(int j=0;j<=lg;j++){
			st[i][j]=min(st[i][j],(1<<j));
			if(v[i]&(1LL<<j))st[i][j+1]=st[i][j];
			else st[i][j+1]=st[i][j]+(1LL<<j);
		}
	}
	int sz=1,gap=1,ans=0,cnt=0,bro=0;
	int mod=sz+gap;
	vector<int>vm;
	for(int k=0;k<=lg;k++){
		sz=(1LL<<k);
		cnt=0;
		bro=0;
		mod=sz+gap;
		vm.clear();
		for(int i=0;i<n;i++)vm.pb(v[i]%mod);
		sort(all(vm));
		for(int i=0;i<n;i++){
			t.update(lb(all(vm),v[i]%mod)-vm.begin(),1);
			if(v[i]&(1LL<<k))C[i]++;
			int l=st[i][k];
			if(v[i]&(1<<k)){
				l+=(1<<k);
				st[i][k]=0;
			}
			int r=l+sz-1;
			l%=mod,r%=mod;
			if(l<=r){
				bro+=t.qry(upper_bound(all(vm),r)-vm.begin()-1)-t.qry(lb(all(vm),l)-vm.begin()-1);
			}
			else{
				swap(l,r);
				l++,r--;
				bro-=t.qry(upper_bound(all(vm),r)-vm.begin()-1)-t.qry(lb(all(vm),l)-vm.begin()-1);
				bro+=i+1;
			}
			//for(int j=0;j<=i;j++)cnt+=between(v[j]%mod,l,r);
		}
		gap+=sz;
		ans+=((bro%2)<<k);
		t.re();
	}
	cout<<ans<<'\n';
}
/*
1 0 0 1 1 0 0 1 1
 
starting sz=1,gap=2
for each k sz=2^k,gapk=gapk-1+2^k-1
starting num=x;
cnt+=valj<i{
	valj>=x
	valj mod (sz+gapk) is between [x mod (sz+gapk),x+sz mod (sz+gapk)]
}
how to find starting num? dp log(n)
*/

Compilation message (stderr)

xorsum.cpp: In function 'void bruteforcecheck()':
xorsum.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=1;i<v.size();i++)if(v[i]-v[i-1]!=1){
      |               ~^~~~~~~~~
xorsum.cpp: In function 'int32_t main()':
xorsum.cpp:108:23: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
  108 |  int sz=1,gap=1,ans=0,cnt=0,bro=0;
      |                       ^~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 38
• Subtask 5: 0 / 23