Submission #73187

#	Time	Username	Problem	Language	Result	Execution time	Memory
73187		shoemakerjo	Secret (JOI14_secret)	C++14	100 / 100	725 ms	5720 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

#define maxn 1010
int n;
int nums[maxn];
int lchild[maxn];
int rchild[maxn];

vector<vector<int>> aft(maxn);
vector<vector<int>> bef(maxn);

//calls to Secret(a, b)

int go(vector<int> stuff) {
	// cout << "going: ";
	// for (int val : stuff) cout << val << " ";
	// cout << endl;
	if (stuff.size() <= 1) return -1;
	//lol complexity does not really matter
	int mid = stuff.size()/2;
	int mval = stuff[mid];

	
	int cval = nums[stuff[mid]];
	for (int i = mid+1; i < stuff.size(); i++) {
		cval = Secret(cval, nums[stuff[i]]);
		aft[mval].push_back(cval);
	}
	if (mid != 0) {
		cval = nums[stuff[mid-1]];
		bef[mval].push_back(cval);
		for (int i = mid-2; i >= 0; i--) {
			cval = Secret(nums[stuff[i]], cval);
			bef[mval].push_back(cval);
		}
	}
	vector<int> lvect, rvect;
	for (int i = 0; i < mid; i++) {
		lvect.push_back(stuff[i]);
	}
	for (int i = mid+1; i < stuff.size(); i++) {
		rvect.push_back(stuff[i]);
	}
	lchild[mval] = go(lvect);
	rchild[mval] = go(rvect);

	return stuff[mid];
}

void Init(int N, int A[]) {
	n = N;
	for (int i = 0; i < n; i++) {
		nums[i] = A[i];
	}
	vector<int> cur;
	for (int i = 0; i < n; i++) {
		cur.push_back(i);
	}
	go(cur);
	// cout << "DONE WITH INIT" << endl;	
}

int Query(int L, int R) {
	if (L == R) return nums[L];
	if (L == R-1) return Secret(nums[L], nums[R]); 
	//why not do this
	int cnode = n/2;
	while (true) {
		if (L <= cnode && cnode <= R) {
			if (L == cnode) {
				return aft[cnode][R-cnode-1];
			}
			if (R == cnode) {
				int fval = bef[cnode][cnode-L-1];
				return Secret(fval, nums[cnode]);
			}
			int fval = bef[cnode][cnode-L-1];
			int sval = aft[cnode][R-cnode-1];
			return Secret(fval, sval);
		}
		if (L > cnode) cnode = rchild[cnode];
		else cnode = lchild[cnode];
	}
}

Compilation message (stderr)

secret.cpp: In function 'int go(std::vector<int>)':
secret.cpp:28:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = mid+1; i < stuff.size(); i++) {
                      ~~^~~~~~~~~~~~~~
secret.cpp:44:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = mid+1; i < stuff.size(); i++) {
                      ~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100