Submission #22535

#TimeUsernameProblemLanguageResultExecution timeMemory
22535dhsrhkdgus (#40)Window Xor (KRIII5_WX)C++14
7 / 7
496 ms5028 KiB
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll,ll> Pll;

#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define repp(i, n) for(int i=1;i<=n;i++)
#define all(x) x.begin(), x.end()

#define ABS(x) (((x) > 0 ) ? (x) : (-(x)))
#define MAX2(x, y) (((x) > (y)) ? (x) : (y))
#define MIN2(x, y) (((x) < (y)) ? (x) : (y))

#define MAX3(x, y, z) ( (x) > (y)  ? ( (x) > (z) ? (x) : (z)  ) : ( (y) > (z) ? (y) : (z) )  )
#define MIN3(x, y, z) ( (x) < (y)  ? ( (x) < (z) ? (x) : (z)  ) : ( (y) < (z) ? (y) : (z) )  )
#define MID3(val1,val2,val3) MAX2(MIN2(MAX2(val1,val2),val3),MIN2(val1,val2))

#define geti1(X) scanf("%d",&X)
#define geti2(X,Y) scanf("%d%d",&X,&Y)
#define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)

#define INF 987654321
#define IINF 987654321987654321

ll N,M,T,K,H;
ll d;

ll fpow(ll x, ll a){
	ll res = 1; ll t = x;
	while( a > 0 ){
		if( a&1 ) res  = ( res * t ) % N;
		t = (t * t) % N;
		a >>= 1;
	}
	return res;
}
int p[100500]; ll L;
ll gcd(ll a, ll b ){
	if( b == 0 ) return a;
	return gcd( b , a % b );
}
int ans[100500]; bool vis[100500];
void solve(int t){
	memset(vis,0,sizeof vis);

	d = fpow(2,t);
	L = N/gcd(d,N);
	rep(i,N)if( !vis[i] ){
		ll tot = 0;
		vector<Pi> v;
		for(int j=0;j<L;j++){
			v.push_back({(i+j*d)%N, p[(i+j*d)%N]});
			vis[(i+j*d)%N] = 1;
			tot ^= v[v.size()-1].Se;
		}
		//for(auto e : v ) printf("%d ",e.Se);
		//printf("\n");
		int a = 0;
		if( (K/L)%2 == 0 ){
			int last = 0;
			for(int j=0;j<K%L;j++){
				a ^= v[j].Se;
				last = j;
			//	printf("%d in %d out \n",v[j].Fi,-1);
			}
			ans[v[0].Fi] = a;
			//printf("%d\n",a);
			for(int j=1;j<=L-1;j++){
				a ^= v[j-1].Se;
				a ^= v[(last+j)%L].Se;

				//printf("%d in %d out \n",v[(last+j)%L].Se,v[j-1].Se);
				ans[v[j].Fi] = a;
			//	printf("%d\n",a);
			}

		}
		else{
			
			int last = -1;
			a = tot;
			for(int j=0;j<K%L;j++){
				a ^= v[j].Se;
				last = j;
			//	printf("%d in %d out \n",v[j].Fi,-1);
			}
			ans[v[0].Fi] = a;
			//cout << last << endl;
			//printf("%d\n",tot);
			for(int j=1;j<=L-1;j++){
				a ^= v[j-1].Se;
				a ^= v[(last+j)%L].Se;
				//printf("!%d %d\n",(last+j)%L, j-1);
				//printf("%d in %d out \n",v[(last+j)%L].Se,v[j-1].Se);
				ans[v[j].Fi] = a;
			//	printf("%d\n",a);
			}
			
		}

	}
	rep(i,N) p[i] = ans[i];
}

int main(void){
	cin >> N >> K >> T;
	rep(i,N) geti(p[i]);
	int k = 0;
	while(T>0){
		if( T & 1 ) solve(k);
		k = k+1;
		T >>= 1;
	}
	rep(i,N) printf("%d ",ans[i]);
}

Compilation message (stderr)

WX.cpp: In function 'int main()':
WX.cpp:132:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i,N) geti(p[i]);
                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...