oj.uz

답안 #535349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535349 2022-03-10T05:06:26 Z assass12 XOR Sum (info1cup17_xorsum) C++14
0 / 100
 1600 ms 9060 KB 
#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;
const int MAX_N = 1000000;
const int MAX_LOGV = 31;
int arr[MAX_N];
int remain[MAX_N];
ll digitNum[MAX_LOGV];
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 flag = ((remain[0]*2)&(1<<digit))==0;
        for(int i=0;i<N;i++){
            //cout<<remain[i]*2<<" , "<<(1<<digit)<<" , "<<((remain[i]*2)&(1<<digit))<<'\n';
            bool newFlag = ((remain[i]*2)&(1<<digit))==0;
            //lo=i;
            if(flag!=newFlag or i==0){
                lo = i;
                while(lo<N and (newFlag^(((remain[i]+remain[lo])&(1<<digit))>0))) lo++;
                hi = lo;
                while(hi<N and (newFlag^(((remain[i]+remain[hi])&(1<<digit))==0))) hi++;
            }else{
                while(lo>i and (newFlag^(((remain[i]+remain[lo-1])&(1<<digit))==0))) lo--;
                while(hi>lo and (newFlag^(((remain[i]+remain[hi-1])&(1<<digit))>0))) hi--;
            }
            digitNum[digit]+= newFlag ? hi-lo : N-i-(hi-lo);
            //cout<<(flag ? 1 : 0)<<" , "<<(newFlag ? 1 : 0)<<" , "<<lo<<" , "<<hi<<" , "<<(newFlag ? hi-lo : N-i-(hi-lo))<<'\n';
            flag = newFlag;
        }
    }
    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;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1697 ms 9060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1697 ms 9060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -