oj.uz

답안 #1115832

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1115832 2024-11-21T02:15:47 Z 8pete8 XOR Sum (info1cup17_xorsum) C++17
7 / 100
 1600 ms 131072 KB 
#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=1e18,minf=-1e18;
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';
		}
	}
}
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);
}
struct seg{
	int T=0;
}t;
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],(1LL<<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;
	int mod=sz+gap;
	for(int k=0;k<=lg;k++){
		sz=(1LL<<k);
		cnt=0;
		mod=sz+gap;
		vector<int>vm;
		for(int i=0;i<n;i++){
			if(v[i]&(1LL<<k))C[i]++;
			int l=st[i][k];
			if(v[i]&(1LL<<k)){
				l+=(1LL<<k);
				st[i][k]=0;
			}
			int r=l+sz-1;
			l%=mod,r%=mod;
			for(int j=0;j<=i;j++)cnt+=between(v[j]%mod,l,r);
		}
		gap+=sz;
		ans+=((cnt%2)<<k);
	}
	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

xorsum.cpp: In function 'void bruteforcecheck()':
xorsum.cpp:53:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long 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){
      |               ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 568 ms 6480 KB Output is correct
2 Correct 579 ms 6480 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 160 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 160 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 568 ms 6480 KB Output is correct
2 Correct 579 ms 6480 KB Output is correct
3 Execution timed out 1668 ms 33064 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 568 ms 6480 KB Output is correct
2 Correct 579 ms 6480 KB Output is correct
3 Runtime error 160 ms 131072 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -