Submission #762085

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
762085	2023-06-20T18:47:49 Z	beaboss	Secret (JOI14_secret)	C++14	Compilation error	0 ms	0 KB

secret

// https://oj.uz/problem/view/JOI14_secret
// 
#include "secret.h"
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

int prefix[1000][1000];

const int MX = 2e5;

int dat[18][MX], mask[MX];

int x[MX];

void divi(int l, int r, int lev) {  // generate dat and mask for [l, r]
	if (l == r) return;
	int m = (l + r) / 2;
	dat[lev][m] = x[m]; // set default lefthand value

	for (int i = m-1; i >= l; i--) dat[lev][i] = Secret(x[i], dat[lev][i + 1]); // gen left hand values

	// same thing for right side
	dat[lev][m + 1] = x[m + 1];
	for (int i = m + 2; i <= r; i++) dat[lev][i] = Secret(dat[lev][i - 1], x[i]);


	for (int i = m + 1; i <= r; i++) mask[i] ^= 1 << lev; // signify with mask that these values we move right
	
	divi(l, m, lev + 1);
	divi(m + 1, r, lev + 1);
}


void Init(int N, int a[]) {
	FOR(i, 0, N) x[i] = a[i];
	divi(0, N-1, 0);
}

int compute(int l, int r) {
	if (l == r) cout << x[l] << endl;
	else {  // find level where info is stored
		// ctz gives number of trailing zeroes
		int bits = __builtin_ctz(mask[l] ^ mask[r]); // how many starting left/right movements are the same
		return Secret(dat[bits][l], dat[bits][r]);
	}
}

Compilation message

secret.cpp: In function 'int compute(int, int)':
secret.cpp:54:30: warning: control reaches end of non-void function [-Wreturn-type]
   54 |  if (l == r) cout << x[l] << endl;
      |                              ^~~~
/usr/bin/ld: /tmp/ccsZAOa4.o: in function `main':
grader-full.cpp:(.text.startup+0x30b): undefined reference to `Query(int, int)'
collect2: error: ld returned 1 exit status