제출 #535674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535674		assass12	XOR Sum (info1cup17_xorsum)	C++14	0 / 100	1689 ms	9044 KiB

xorsum

#pragma GCC optimize("O3")
#include <unistd.h>
#include <bits/stdc++.h>
using namespace std;
namespace io {
	const signed IS=1<<20, OS=1<<18;
	char I[IS*32+1],*J=I,O[OS],*K=O;

	inline void daer(){if(J>=I+IS-64){char*p=I;do*p++=*J++;while(J!=I+IS);p[read(0,p,I+IS-p)]=0;J=I;}}
	template<int N=10,typename T=int>inline T getu(){daer();T x=0;int k=0;do x=x*10+*J-'0';while(*++J>='0'&&++k<N);++J;return x;}
	template<int N=10,typename T=int>inline T geti(){daer();bool e=*J=='-';J+=e;return(e?-1:1)*getu<N,T>();}
	inline void flush(){write(1,O,K-O);K=O;}

	template<int N=10,typename T=int>inline void putu(T n){char s[(N+7)/8*8],*p=s;int k=0;do*p++=n%10+48;while((n/=10)&&++k<N);do*K++=*--p;while(p!=s);*K++=10;if(K>=O+OS-64)flush();}
	template<int N=10,typename T=int>inline void puti(T n){if(n<0)*K++='-',n=-n;putu<N,T>(n);}
	struct f{f(){I[read(0,I,IS)]=0;}~f(){flush();}}flu;
};
using namespace io;
typedef long long ll;
typedef pair<int,int> pii;
const int MAX_N = 1000000;
const int MAX_LOGV = 31;
int arr[MAX_N];
int remain[MAX_N];
ll digitNum[MAX_LOGV];
int binarySearch(int i,int digit,int lo,int hi,int loFlag,int hiFlag){
    assert(loFlag!=hiFlag and lo<hi);
    while(lo+1<hi){
        int mid = (lo+hi)/2;
        if((((remain[i]+remain[mid])&(1<<digit))==0)==loFlag){
            lo = mid;
        }else{
            hi = mid;
        }
    }
    return hi;
}
int searchLo(int i,int digit,int N,bool loFlag){
    int lo = i;
    while(lo<N and loFlag==(((remain[i]+remain[lo])&(1<<digit))==0)) lo++;
    return lo;
}

void run(){
    int N = getu<7>();
    memset(digitNum,0,sizeof(digitNum));
    for(int i=0;i<N;i++){
        arr[i] = getu<9>();
    }
    for(int digit=0;digit<MAX_LOGV;digit++){
        for(int i=0;i<N;i++){
            remain[i] = arr[i]&((1<<(digit+1))-1);
        }
        sort(remain,remain+N);
        //for(int i=0;i<4;i++)cout<<remain[i]<<" ";
        //cout<<'\n';
        int lo=0,hi=0;bool loFlag = ((remain[0]*2)&(1<<digit))==0;
        bool hiFlag = ((remain[0]+remain[N-1])&(1<<digit))==0;
        if(loFlag!=hiFlag){
            lo = binarySearch(0,digit,0,N-1,loFlag,hiFlag);
            hi = N;
        }else{
            lo = searchLo(0,digit,N,loFlag);
            hi = lo==N ? N : binarySearch(0,digit,lo,N-1,!loFlag,hiFlag);
        }
        digitNum[digit]+= loFlag ? hi-lo : N-(hi-lo);
        //cout<<(loFlag ? 1 : 0)<<" , "<<lo<<" , "<<hi<<" , "<<(loFlag ? hi-lo : N-(hi-lo))<<'\n';
        for(int i=1;i<N;i++){
            //cout<<remain[i]*2<<" , "<<(1<<digit)<<" , "<<((remain[i]*2)&(1<<digit))<<'\n';
            bool newLoFlag = ((remain[i]*2)&(1<<digit))==0;
            hiFlag = ((remain[i]+remain[N-1])&(1<<digit))==0;
            if(loFlag==newLoFlag){
                if(newLoFlag==hiFlag){
                    //lo = lo==N ? searchLo(i,digit,N,newLoFlag) : binarySearch(i,digit,i,lo,newLoFlag,!newLoFlag);
                    lo = searchLo(i,digit,N,newLoFlag);
                    hi = lo==N ? N : binarySearch(i,digit,lo,N-1,!newLoFlag,hiFlag);
                }else{
                    assert(hi==N);
                    lo = binarySearch(i,digit,i,N-1,newLoFlag,hiFlag);
                }
            }else{
                if(newLoFlag==hiFlag){
                    lo = lo==N ? searchLo(i,digit,N,newLoFlag) : binarySearch(i,digit,i,hi,newLoFlag,!newLoFlag);
                    hi = lo==N ? N : binarySearch(i,digit,lo,N-1,!newLoFlag,hiFlag);
                }else{
                    lo = binarySearch(i,digit,i,N-1,newLoFlag,hiFlag);
                    hi = N;
                }
            }
            digitNum[digit]+= newLoFlag ? hi-lo : N-i-(hi-lo);
            //cout<<(loFlag ? 1 : 0)<<" , "<<(newLoFlag ? 1 : 0)<<" , "<<lo<<" , "<<hi<<" , "<<(newLoFlag ? hi-lo : N-i-(hi-lo))<<'\n';
            loFlag = newLoFlag;
        }
    }
    int ret = 0;
    for(int digit=0;digit<MAX_LOGV;digit++){
        ret+= (digitNum[digit]&1) ? (1<<digit) : 0;
    }
    putu(ret);
}


int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    //cout.tie(NULL);
    run();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

xorsum.cpp: In function 'void io::flush()':
xorsum.cpp:12:27: warning: ignoring return value of 'ssize_t write(int, const void*, size_t)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  inline void flush(){write(1,O,K-O);K=O;}
      |                      ~~~~~^~~~~~~~~

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