oj.uz

Submission #1008577

# Submission time Handle Problem Language Result Execution time Memory
1008577 2024-06-26T14:37:48 Z Math4Life2020 Magic Show (APIO24_show) C++17
35 / 100
 5 ms 824 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;
ll N = 5000;
ll E = 40; 

ld seed = 0.697810983;
ld getseed() {
	seed = 3.60*seed*(1.0-seed);
	return seed;
}

ll getrng(ll x) { //random integer in [0,x-1]
	return (((ll) round(1912873139*getseed()))%x);
}

ll l2(ll x) {
	return (31-__builtin_clz(x));
}

vector<pair<int,int>> Alice() {
	ll X = setN(N);
	vector<pair<int,int>> vout;
	vector<ll> xv;
	for (ll e=(E-1);e>=0;e--) {
		xv.push_back((X>>e)%2);
	}
	for (ll n=1;n<N;n++) {
		ll D = l2(n)-1;
		ll val = 0;
		for (ll d=0;d<D;d++) {
			ll e = getrng(E);
			val += xv[e]*(1LL<<d);
		}
		vout.push_back({val+1,n+1});
	}
	return vout;
}

long long Bob(vector<pair<int,int>> V) {
	ll vals[N];
	for (ll i=0;i<N;i++) {
		vals[i]=-1;
	}
	for (pii p0: V) {
		vals[p0.second-1]=p0.first-1;
	}
	vector<ll> xv;
	for (ll e=(E-1);e>=0;e--) {
		xv.push_back(0);
	}
	for (ll n=1;n<N;n++) {
		ll D = l2(n)-1;
		for (ll d=0;d<D;d++) {
			ll e = getrng(E);
			//val += xv[e]*(1LL<<d);
			if (vals[n]!=-1) {
				xv[e]=(vals[n]>>d)%(2LL);
			}
		}
	}
	ll X = 0;
	for (ll e=0;e<E;e++) {
		X += xv[e]*((ll) (1LL<<(E-1-e)));
	}
	return X;
}
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;
ll N = 5000;
ll E = 40; 

ld seed = 0.697810983;
ld getseed() {
	seed = 3.60*seed*(1.0-seed);
	return seed;
}

ll getrng(ll x) { //random integer in [0,x-1]
	return (((ll) round(1912873139*getseed()))%x);
}

ll l2(ll x) {
	return (31-__builtin_clz(x));
}


long long Bob(vector<pair<int,int>> V) {
	ll vals[N];
	for (ll i=0;i<N;i++) {
		vals[i]=-1;
	}
	for (pii p0: V) {
		vals[p0.second-1]=p0.first-1;
	}
	vector<ll> xv;
	for (ll e=(E-1);e>=0;e--) {
		xv.push_back(0);
	}
	for (ll n=1;n<N;n++) {
		ll D = l2(n)-1;
		for (ll d=0;d<D;d++) {
			ll e = getrng(E);
			//val += xv[e]*(1LL<<d);
			if (vals[n]!=-1) {
				xv[e]=(vals[n]>>d)%(2LL);
			}
		}
	}
	ll X = 0;
	for (ll e=0;e<E;e++) {
		X += xv[e]*((ll) (1LL<<(E-1-e)));
	}
	return X;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 812 KB Correct.
2 Correct 3 ms 824 KB Correct.
3 Correct 3 ms 812 KB Correct.
4 Correct 4 ms 824 KB Correct.
5 Correct 4 ms 808 KB Correct.
6 Correct 4 ms 808 KB Correct.
7 Correct 3 ms 820 KB Correct.
8 Correct 4 ms 824 KB Correct.
9 Correct 3 ms 812 KB Correct.
10 Correct 3 ms 812 KB Correct.
11 Correct 3 ms 820 KB Correct.
12 Correct 4 ms 808 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 812 KB Correct.
2 Correct 3 ms 824 KB Correct.
3 Correct 3 ms 812 KB Correct.
4 Correct 4 ms 824 KB Correct.
5 Correct 4 ms 808 KB Correct.
6 Correct 4 ms 808 KB Correct.
7 Correct 3 ms 820 KB Correct.
8 Correct 4 ms 824 KB Correct.
9 Correct 3 ms 812 KB Correct.
10 Correct 3 ms 812 KB Correct.
11 Correct 3 ms 820 KB Correct.
12 Correct 4 ms 808 KB Correct.
13 Correct 4 ms 820 KB Correct.
14 Correct 4 ms 816 KB Correct.
15 Correct 4 ms 820 KB Correct.
16 Correct 3 ms 816 KB Correct.
17 Correct 3 ms 816 KB Correct.
18 Correct 3 ms 816 KB Correct.
19 Correct 3 ms 816 KB Correct.
20 Correct 3 ms 816 KB Correct.
21 Correct 4 ms 816 KB Correct.
22 Correct 3 ms 816 KB Correct.
23 Correct 3 ms 820 KB Correct.
24 Correct 3 ms 816 KB Correct.

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 812 KB Correct.
2 Correct 3 ms 824 KB Correct.
3 Correct 3 ms 812 KB Correct.
4 Correct 4 ms 824 KB Correct.
5 Correct 4 ms 808 KB Correct.
6 Correct 4 ms 808 KB Correct.
7 Correct 3 ms 820 KB Correct.
8 Correct 4 ms 824 KB Correct.
9 Correct 3 ms 812 KB Correct.
10 Correct 3 ms 812 KB Correct.
11 Correct 3 ms 820 KB Correct.
12 Correct 4 ms 808 KB Correct.
13 Correct 4 ms 820 KB Correct.
14 Correct 4 ms 816 KB Correct.
15 Correct 4 ms 820 KB Correct.
16 Correct 3 ms 816 KB Correct.
17 Correct 3 ms 816 KB Correct.
18 Correct 3 ms 816 KB Correct.
19 Correct 3 ms 816 KB Correct.
20 Correct 3 ms 816 KB Correct.
21 Correct 4 ms 816 KB Correct.
22 Correct 3 ms 816 KB Correct.
23 Correct 3 ms 820 KB Correct.
24 Correct 3 ms 816 KB Correct.
25 Incorrect 4 ms 816 KB Incorrect answer.
26 Halted 0 ms 0 KB -