# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
990848 | abczz | Broken Device (JOI17_broken_device) | C++14 | 31 ms | 2896 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Annalib.h"
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
void Anna( int N, long long X, int K, int P[] ){
mt19937_64 mt(69);
ll perm[150];
for (int i=0; i<N; ++i) {
perm[i] = i;
}
shuffle(perm, perm+N, mt);
ll x = 805215019090496300;
bool B[150], F[150];
for (int i=0; i<N; ++i) B[i] = F[i] = 0;
for (int i=0; i<K; ++i) B[P[i]] = 1;
x ^= X;
ll p = 0;
for (int i=59; i>=0; --i) {
ll bit = (bool)(x & (1LL<<i));
for (int j=bit; j<N; j+=2) {
if (p+j >= N) break;
if (!B[perm[p+j]]) {
//cout << p+j << " ";
//cout << i << " " << j << endl;
//cout << j << " ";
F[perm[p+j]] = 1;
p += j+1;
break;
}
}
}
//cout << endl;
for (int i=0; i<N; ++i) {
Set(i, F[i]);
}
}
#include "Brunolib.h"
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#define ll long long
using namespace std;
long long Bruno( int N, int A[] ){
mt19937_64 mt(69);
vector <ll> V;
ll perm[150], par[150];
for (int i=0; i<N; ++i) {
perm[i] = i;
}
shuffle(perm, perm+N, mt);
for (int i=0; i<N; ++i) {
par[perm[i]] = i;
}
ll x = 805215019090496300;
ll p = 0;
for (int i=0; i<N; ++i) {
if (A[i]) {
V.push_back(par[i]);
}
}
sort(V.begin(), V.end());
int j = 0;
for (int i=59; i>=0; --i) {
//cout << V[j]-p << " ";
if ((bool)((V[j]-p) & 1)) x ^= (1LL<<i);
p = V[j++]+1;
if (j == V.size()) break;
}
//cout << endl;
//cout << x << endl;
return x;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |