oj.uz

Submission #420661

# Submission time Handle Problem Language Result Execution time Memory
420661 2021-06-08T13:12:53 Z Kevin_Zhang_TW Broken Device (JOI17_broken_device) C++17
100 / 100
 61 ms 2584 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;
#include "Annalib.h"

const int wid = 38;
// I try to send 39 blocks of information
// But If I want the information to be reversed, I'll send 40 blocks, with the first one meaningless
void Anna( int N, long long X, int K, int P[] ){
	vector<int> bad(N), rbad;
	for (int i = 0;i < K;++i)
		bad[ P[i] ] = true;
	rbad = bad; reverse(AI(rbad));

	vector<int> x3;
	for (ll i = 0, v = X;i < wid;++i) {
		x3.pb(v % 3), v /= 3;
	}

	// I'll send normal information
	auto gen_nor = [&](vector<int> bad) {
		vector<int> res(N);

		int good = 0, a = 0;
		auto valid = [&](int i, int j, int v) {
			if (v == 0) return !bad[j];
			if (v == 1) return !bad[i];
			return !bad[i] && !bad[j];
		};
		auto go_fill = [&](int i, int j, int v) {
			res[i] = v != 0;
			res[j] = v != 1;
		};
		for (int ad = 0;ad < 3;++ad) {
			vector<int> xbit(x3);
			for (int &i : xbit) i = (i + ad) % 3;
			int cnt = 0;
			for (int i = 0;i < wid * 2;i += 2) {
				if (valid(i, i+1, xbit[i/2]))
					++cnt;
			}
			if (chmax(good, cnt))
				a = ad;
		}
		//a = 0, good = 0;

		vector<int> to_send(x3);
		for (int &i : to_send) i = (i + a) % 3;

		to_send.pb(a);
		debug(AI(to_send));

		for (int i = 0;i < wid*2;i += 2) {
			if (valid(i, i+1, to_send[i/2])) {
				go_fill(i, i+1, to_send[i/2]);
				to_send[i/2] = -1;
			}
		}
		vector<int> lft;
		for (int &i : to_send) if (i != -1)
			lft.pb(i);

		debug(AI(lft));

		reverse(AI(lft));

		for (int i = wid*2;i < N;i += 2) {
			if (lft.empty()) break;
			if (valid(i, i+1, lft.back())) {
				go_fill(i, i+1, lft.back());
				lft.pop_back();
			}
		}

		return res;
	};

	auto a = gen_nor(bad);
	auto b = gen_nor(rbad); reverse(AI(b));

   	for (int i = 0;i < N;++i)
		if (!bad[i]) {
			b[i] = true;
			break;
		}

	vector<int> res;

	if (count(begin(bad), begin(bad) + N/2, true) >= 20) {
		res = a;
	}
	else res = b;

	DE(X);
	debug(AI(res));
	for (int i = 0;i < N;++i)
			Set(i, res[i]);

}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
namespace {
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
}
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;
#include "Brunolib.h"

const int wid = 38;

long long Bruno( int N, int A[] ){

	int valid_cnt = 0;
	for (int i = 0;i < N;i += 2) {
		if (A[i] || A[i+1]) ++valid_cnt;
	}

	if (valid_cnt == 40) {
		for (int i = 0;i < N;i += 2) {
			if (A[i] || A[i+1]) {
				A[i] = A[i+1] = false;
				break;
			}
		}
		reverse(A, A + N);
	}
	// then read it

	int state[2][2]{};

	memset(state, -1, sizeof(state));
	state[0][1] = 0;
	state[1][0] = 1;
	state[1][1] = 2;

	vector<int> bit(wid + 1, -1);
	for (int i = 0;i < wid * 2;i += 2) {
		DE(A[i], A[i+1]);
		bit[i/2] = state[ A[i] ][ A[i+1] ];
	}

	debug(AI(bit));

	for (int i = wid*2;i < N;i += 2) {
		if (A[i] || A[i+1]) {
			int val = state[A[i]][A[i+1]];
			for (int &j : bit) {
				if (j == -1) {
					j = val;
					break;
				}
			}
		}
	}

	for (int i = 0;i < wid;++i) {
		bit[i] = (bit[i] + 3 - bit.back()) % 3;
	}

	bit.resize(wid);

	reverse(AI(bit));

	ll ret = 0;
	for (int i : bit)
		ret = (ret * 3) + i;

	DE(ret);
	return ret;

}

Compilation message

Anna.cpp: In lambda function:
Anna.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Anna.cpp:66:3: note: in expansion of macro 'debug'
   66 |   debug(AI(to_send));
      |   ^~~~~
Anna.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Anna.cpp:78:3: note: in expansion of macro 'debug'
   78 |   debug(AI(lft));
      |   ^~~~~
Anna.cpp: In function 'void Anna(int, long long int, int, int*)':
Anna.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
Anna.cpp:109:2: note: in expansion of macro 'DE'
  109 |  DE(X);
      |  ^~
Anna.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Anna.cpp:110:2: note: in expansion of macro 'debug'
  110 |  debug(AI(res));
      |  ^~~~~

Bruno.cpp: In function 'long long int Bruno(int, int*)':
Bruno.cpp:16:17: warning: statement has no effect [-Wunused-value]
   16 | #define DE(...) 0
      |                 ^
Bruno.cpp:52:3: note: in expansion of macro 'DE'
   52 |   DE(A[i], A[i+1]);
      |   ^~
Bruno.cpp:17:20: warning: statement has no effect [-Wunused-value]
   17 | #define debug(...) 0
      |                    ^
Bruno.cpp:56:2: note: in expansion of macro 'debug'
   56 |  debug(AI(bit));
      |  ^~~~~
Bruno.cpp:16:17: warning: statement has no effect [-Wunused-value]
   16 | #define DE(...) 0
      |                 ^
Bruno.cpp:82:2: note: in expansion of macro 'DE'
   82 |  DE(ret);
      |  ^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2484 KB Output is correct - L* = 40
2 Correct 49 ms 2532 KB Output is correct - L* = 40
3 Correct 54 ms 2476 KB Output is correct - L* = 40
4 Correct 50 ms 2444 KB Output is correct - L* = 40
5 Correct 47 ms 2584 KB Output is correct - L* = 40
6 Correct 60 ms 2552 KB Output is correct - L* = 40
7 Correct 47 ms 2540 KB Output is correct - L* = 40
8 Correct 53 ms 2504 KB Output is correct - L* = 40
9 Correct 47 ms 2516 KB Output is correct - L* = 40
10 Correct 53 ms 2452 KB Output is correct - L* = 40
11 Correct 47 ms 2556 KB Output is correct - L* = 40
12 Correct 54 ms 2396 KB Output is correct - L* = 40
13 Correct 51 ms 2512 KB Output is correct - L* = 40
14 Correct 48 ms 2496 KB Output is correct - L* = 40
15 Correct 46 ms 2476 KB Output is correct - L* = 40
16 Correct 47 ms 2488 KB Output is correct - L* = 40
17 Correct 61 ms 2408 KB Output is correct - L* = 40
18 Correct 50 ms 2444 KB Output is correct - L* = 40
19 Correct 48 ms 2512 KB Output is correct - L* = 40
20 Correct 49 ms 2460 KB Output is correct - L* = 40
21 Correct 59 ms 2392 KB Output is correct - L* = 40
22 Correct 55 ms 2472 KB Output is correct - L* = 40
23 Correct 46 ms 2512 KB Output is correct - L* = 40
24 Correct 47 ms 2556 KB Output is correct - L* = 40
25 Correct 47 ms 2396 KB Output is correct - L* = 40
26 Correct 56 ms 2476 KB Output is correct - L* = 40
27 Correct 56 ms 2496 KB Output is correct - L* = 40
28 Correct 49 ms 2460 KB Output is correct - L* = 40
29 Correct 47 ms 2512 KB Output is correct - L* = 40
30 Correct 49 ms 2548 KB Output is correct - L* = 40
31 Correct 50 ms 2408 KB Output is correct - L* = 40
32 Correct 48 ms 2444 KB Output is correct - L* = 40
33 Correct 47 ms 2452 KB Output is correct - L* = 40
34 Correct 46 ms 2476 KB Output is correct - L* = 40
35 Correct 53 ms 2392 KB Output is correct - L* = 40
36 Correct 48 ms 2396 KB Output is correct - L* = 40
37 Correct 47 ms 2460 KB Output is correct - L* = 40
38 Correct 48 ms 2468 KB Output is correct - L* = 40
39 Correct 47 ms 2420 KB Output is correct - L* = 40
40 Correct 47 ms 2432 KB Output is correct - L* = 40