Submission #22515

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22515	2017-04-30T05:15:35 Z	dhsrhkdgus(#943, kjp4155, cok1973, dhsrhkdgus)	Window Xor (KRIII5_WX)	C++14	0 / 7	463 ms	5028 KB

WX

#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 = 0;
			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;
			//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);
			}
			
		}

	}
	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

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

Subtask #1

0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2904 KB	Output is correct
2	Correct	0 ms	2904 KB	Output is correct
3	Correct	0 ms	2904 KB	Output is correct
4	Correct	263 ms	5028 KB	Output is correct
5	Correct	26 ms	4524 KB	Output is correct
6	Correct	289 ms	4524 KB	Output is correct
7	Correct	29 ms	4524 KB	Output is correct
8	Correct	273 ms	4524 KB	Output is correct
9	Correct	276 ms	4524 KB	Output is correct
10	Correct	263 ms	5028 KB	Output is correct
11	Correct	259 ms	5028 KB	Output is correct
12	Correct	283 ms	3756 KB	Output is correct
13	Correct	333 ms	3756 KB	Output is correct
14	Correct	169 ms	4004 KB	Output is correct
15	Correct	153 ms	4004 KB	Output is correct
16	Correct	463 ms	4524 KB	Output is correct
17	Incorrect	449 ms	4524 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	269 ms	4524 KB	Output is correct
2	Correct	139 ms	3044 KB	Output is correct
3	Correct	183 ms	4524 KB	Output is correct
4	Correct	279 ms	4524 KB	Output is correct
5	Correct	279 ms	4524 KB	Output is correct
6	Correct	146 ms	5028 KB	Output is correct
7	Correct	149 ms	5028 KB	Output is correct
8	Correct	256 ms	4524 KB	Output is correct
9	Correct	256 ms	4524 KB	Output is correct
10	Correct	289 ms	3756 KB	Output is correct
11	Correct	76 ms	4004 KB	Output is correct
12	Correct	79 ms	4004 KB	Output is correct
13	Correct	23 ms	3176 KB	Output is correct
14	Correct	23 ms	3176 KB	Output is correct
15	Correct	283 ms	4524 KB	Output is correct
16	Correct	23 ms	3176 KB	Output is correct
17	Correct	263 ms	4524 KB	Output is correct
18	Correct	33 ms	3176 KB	Output is correct
19	Incorrect	266 ms	4524 KB	Output isn't correct
20	Halted	0 ms	0 KB	-