oj.uz

Submission #55050

# Submission time Handle Problem Language Result Execution time Memory
55050 2018-07-05T23:06:57 Z ksun48 Broken Device (JOI17_broken_device) C++14
0 / 100
 197 ms 4032 KB 
#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

void done(vector<LL> message, vector<LL> perm){
	for(int i = 0; i < message.size(); i++){
		Set(i, message[perm[i]]);
		//cout << message[i];
	}
	//cout << '\n';
}

int make(vector<LL> duds){
	return duds[1]*(duds[1]+1)/2 + duds[0];
}

void Anna(int N, long long X, int K, int P[]){

	// shared initialization
	static mt19937_64 mt1(4848);
	static mt19937_64 mt2(48484899);
	static LL B = 60;
	LL Y = mt1() & ((1LL << B) - 1);
	vector<LL> perm(N);
	for(int i = 0; i < N; i++){
		perm[i] = i;
	}
	for(int i = N-1; i >= 0; i--){
		int d = mt2() % (i+1);
		if(d < 0){
			d += (i+1);
		}
		swap(perm[i], perm[d]);
	}
	// shared initialization

	vector<LL> info(60);
	for(LL i = 0; i < 60; i++){
		info[i] = ((X ^ Y) >> i) & 1;
	}

	vector<LL> message(N, 0);
	// boilerplate
	// ----------------------------------

	vector<LL> bad(N, 0);
	for(int i = 0; i < K; i++){
		bad[perm[P[i]]] = 1;
	}
	int cur = 0;
	vector<LL> duds;

	//cout << "Anna " << K << '\n';
	for(int i = 0; i < 60; i++){
		if(info[i] && bad[cur] && bad[cur+1]){
			duds.push_back(i+1);
			//cout << "dud " << i << '\n';
		}
		message[cur++] = info[i];
		message[cur++] = info[i];
		if(cur == 150){
			done(message, perm);
			return;
		}
	}

	duds.resize(2, 0); // 0 -> 60
	sort(duds.begin(), duds.end());

	int f = make(duds);
	vector<LL> g;
	for(int j = 0; j < 11; j++){
		g.push_back(f % 2);
		f /= 2;
	}
	reverse(g.begin(), g.end());
	vector<LL> newduds;
	for(int q = 0; q < g.size(); q++){
		if(g[q] && bad[cur] && bad[cur+1]){
			newduds.push_back(q+1);
		}
		message[cur++] = g[q];
		message[cur++] = g[q];
		if(cur == 150){
			done(message, perm);
			return;
		}
	}
	int f2 = 0;
	if(newduds.size() > 0) f2 = newduds[0];
	vector<LL> g2;
	for(int j = 0; j < 4; j++){
		g2.push_back(f2 % 2);
		f2 /= 2;
	}
	reverse(g2.begin(), g2.end());
	for(int q = 0; q < g2.size(); q++){
		message[cur++] = g2[q];
		message[cur++] = g2[q];
		if(cur == 150){
			done(message, perm);
			return;
		}
	}

	// ----------------------------------
	done(message, perm);
}

#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

using namespace std;

LL done(vector<LL> info, LL b){
	LL a = 0;
	for(LL i = 0; i < 60; i++){
		a ^= info[i] << i;
	}
	return a ^ b;
}

vector<int> solve(int x){
	vector<int> ans;
	for(int b = 0; b < 100; b++){
		if(b * (b+1)/2 <= x && (b+1) * (b+2)/2 > x){
			int a = x - b * (b+1)/2;
			if(a != 0) ans.push_back(a);
			if(b != 0) ans.push_back(b);
			return ans;
		}
	}
}

long long Bruno(int N, int A[]){
	return 0LL;

	// shared initialization
	static mt19937_64 mt1(4848);
	static mt19937_64 mt2(48484899);
	static LL B = 60;
	LL Y = mt1() & ((1LL << B) - 1);
	vector<LL> perm(N);
	for(int i = 0; i < N; i++){
		perm[i] = i;
	}
	for(int i = N-1; i >= 0; i--){
		int d = mt2() % (i+1);
		if(d < 0){
			d += (i+1);
		}
		swap(perm[i], perm[d]);
	}
	// shared initialization

	vector<LL> message(N);
	for(int i = 0; i < N; i++){
		message[perm[i]] = A[i];
	}

	vector<LL> info(60, 0);
	// boilerplate
	// ----------------------------------

	for(int i = 0; i < N; i++){
		//cout << message[i];
	}
	//cout << '\n';

	int cur = 0;

	for(int i = 0; i < 60; i++){
		info[i] = max(info[i], message[cur++]);
		info[i] = max(info[i], message[cur++]);
	}


	vector<LL> dudbits(11, 0);
	for(int i = 0; i < 11; i++){
		dudbits[i] = max(dudbits[i], message[cur++]);
		dudbits[i] = max(dudbits[i], message[cur++]);
	}

	vector<LL> dudbits2(4, 0);
	for(int i = 0; i < 4; i++){
		dudbits2[i] = max(dudbits2[i], message[cur++]);
		dudbits2[i] = max(dudbits2[i], message[cur++]);
	}
	int dud = 0;
	for(int j = 0; j < 4; j++){
		dud = (dud << 1) + dudbits2[j];
	}
	dud--;
	if(dud != -1){
		dudbits[dud] = 1;
	}

	int num = 0;
	for(int j = 0; j < 11; j++){
		num = (num << 1) + dudbits[j];
	}
	vector<int> duds = solve(num);
	for(int a : duds){
		info[a-1] = 1;
	}

	// ----------------------------------
	return done(info, Y);
}

Compilation message

Anna.cpp: In function 'void done(std::vector<long long int>, std::vector<long long int>)':
Anna.cpp:7:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < message.size(); i++){
                 ~~^~~~~~~~~~~~~~~~
Anna.cpp: In function 'void Anna(int, long long int, int, int*)':
Anna.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int q = 0; q < g.size(); q++){
                 ~~^~~~~~~~~~
Anna.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int q = 0; q < g2.size(); q++){
                 ~~^~~~~~~~~~~

Bruno.cpp: In function 'std::vector<int> solve(int)':
Bruno.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 3056 KB Output isn't correct - L* = 0
2 Incorrect 50 ms 3632 KB Output isn't correct - L* = 0
3 Incorrect 66 ms 3752 KB Output isn't correct - L* = 0
4 Incorrect 46 ms 3752 KB Output isn't correct - L* = 0
5 Incorrect 45 ms 3752 KB Output isn't correct - L* = 0
6 Incorrect 47 ms 3752 KB Output isn't correct - L* = 0
7 Incorrect 50 ms 3840 KB Output isn't correct - L* = 0
8 Incorrect 197 ms 3840 KB Output isn't correct - L* = 0
9 Incorrect 55 ms 3840 KB Output isn't correct - L* = 0
10 Incorrect 51 ms 3840 KB Output isn't correct - L* = 0
11 Incorrect 57 ms 3840 KB Output isn't correct - L* = 0
12 Incorrect 63 ms 3840 KB Output isn't correct - L* = 0
13 Incorrect 56 ms 3840 KB Output isn't correct - L* = 0
14 Incorrect 63 ms 3840 KB Output isn't correct - L* = 0
15 Incorrect 73 ms 3840 KB Output isn't correct - L* = 0
16 Incorrect 45 ms 4024 KB Output isn't correct - L* = 0
17 Incorrect 45 ms 4024 KB Output isn't correct - L* = 0
18 Incorrect 61 ms 4024 KB Output isn't correct - L* = 0
19 Incorrect 62 ms 4024 KB Output isn't correct - L* = 0
20 Incorrect 80 ms 4024 KB Output isn't correct - L* = 0
21 Incorrect 58 ms 4024 KB Output isn't correct - L* = 0
22 Incorrect 83 ms 4024 KB Output isn't correct - L* = 0
23 Incorrect 54 ms 4024 KB Output isn't correct - L* = 0
24 Incorrect 54 ms 4024 KB Output isn't correct - L* = 0
25 Incorrect 52 ms 4024 KB Output isn't correct - L* = 0
26 Incorrect 53 ms 4024 KB Output isn't correct - L* = 0
27 Incorrect 49 ms 4024 KB Output isn't correct - L* = 0
28 Incorrect 45 ms 4024 KB Output isn't correct - L* = 0
29 Incorrect 47 ms 4024 KB Output isn't correct - L* = 0
30 Incorrect 47 ms 4024 KB Output isn't correct - L* = 0
31 Incorrect 45 ms 4032 KB Output isn't correct - L* = 0
32 Incorrect 97 ms 4032 KB Output isn't correct - L* = 0
33 Incorrect 63 ms 4032 KB Output isn't correct - L* = 0
34 Incorrect 51 ms 4032 KB Output isn't correct - L* = 0
35 Incorrect 53 ms 4032 KB Output isn't correct - L* = 0
36 Incorrect 46 ms 4032 KB Output isn't correct - L* = 0
37 Incorrect 45 ms 4032 KB Output isn't correct - L* = 0
38 Incorrect 45 ms 4032 KB Output isn't correct - L* = 0
39 Incorrect 45 ms 4032 KB Output isn't correct - L* = 0
40 Incorrect 52 ms 4032 KB Output isn't correct - L* = 0