oj.uz

Submission #55049

# Submission time Handle Problem Language Result Execution time Memory
55049 2018-07-05T23:03:56 Z ksun48 Broken Device (JOI17_broken_device) C++14
0 / 100
 96 ms 4672 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(484848);
	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];
	}
	for(int i = 0; i < 60; i++){
		//cout << info[i];
	}
	//cout << '\n';

	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[]){

	// shared initialization
	static mt19937_64 mt1(4848);
	static mt19937_64 mt2(484848);
	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);
	//cout << "Bruno " << '\n';
	for(int a : duds){
		//cout << a-1 << '\n';
		info[a-1] = 1;
	}

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

	// ----------------------------------
	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 Partially correct 52 ms 3056 KB Output is partially correct - L* = 24
2 Partially correct 80 ms 3312 KB Output is partially correct - L* = 23
3 Partially correct 57 ms 3720 KB Output is partially correct - L* = 17
4 Partially correct 56 ms 3784 KB Output is partially correct - L* = 17
5 Partially correct 55 ms 3784 KB Output is partially correct - L* = 22
6 Partially correct 51 ms 3832 KB Output is partially correct - L* = 19
7 Partially correct 53 ms 3840 KB Output is partially correct - L* = 23
8 Runtime error 40 ms 3840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Partially correct 56 ms 4552 KB Output is partially correct - L* = 15
10 Partially correct 57 ms 4552 KB Output is partially correct - L* = 15
11 Partially correct 54 ms 4552 KB Output is partially correct - L* = 21
12 Partially correct 52 ms 4552 KB Output is partially correct - L* = 19
13 Runtime error 76 ms 4552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Partially correct 96 ms 4552 KB Output is partially correct - L* = 14
15 Partially correct 88 ms 4552 KB Output is partially correct - L* = 19
16 Runtime error 45 ms 4552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Partially correct 62 ms 4552 KB Output is partially correct - L* = 23
18 Runtime error 53 ms 4552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Partially correct 58 ms 4552 KB Output is partially correct - L* = 23
20 Partially correct 55 ms 4552 KB Output is partially correct - L* = 15
21 Partially correct 71 ms 4552 KB Output is partially correct - L* = 19
22 Partially correct 51 ms 4552 KB Output is partially correct - L* = 23
23 Partially correct 60 ms 4656 KB Output is partially correct - L* = 22
24 Partially correct 56 ms 4656 KB Output is partially correct - L* = 19
25 Partially correct 51 ms 4656 KB Output is partially correct - L* = 24
26 Partially correct 65 ms 4656 KB Output is partially correct - L* = 22
27 Partially correct 71 ms 4672 KB Output is partially correct - L* = 21
28 Partially correct 56 ms 4672 KB Output is partially correct - L* = 23
29 Partially correct 63 ms 4672 KB Output is partially correct - L* = 18
30 Partially correct 63 ms 4672 KB Output is partially correct - L* = 18
31 Partially correct 52 ms 4672 KB Output is partially correct - L* = 20
32 Partially correct 53 ms 4672 KB Output is partially correct - L* = 24
33 Partially correct 57 ms 4672 KB Output is partially correct - L* = 16
34 Partially correct 50 ms 4672 KB Output is partially correct - L* = 19
35 Partially correct 57 ms 4672 KB Output is partially correct - L* = 22
36 Runtime error 51 ms 4672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Partially correct 52 ms 4672 KB Output is partially correct - L* = 20
38 Partially correct 53 ms 4672 KB Output is partially correct - L* = 21
39 Partially correct 63 ms 4672 KB Output is partially correct - L* = 17
40 Partially correct 67 ms 4672 KB Output is partially correct - L* = 16