oj.uz

Submission #73187

# Submission time Handle Problem Language Result Execution time Memory
73187 2018-08-28T03:46:57 Z shoemakerjo Secret (JOI14_secret) C++14
100 / 100
 725 ms 5720 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 2552 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 204 ms 2896 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 209 ms 2896 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 712 ms 5244 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 668 ms 5244 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 725 ms 5340 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 699 ms 5720 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 685 ms 5720 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 690 ms 5720 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 707 ms 5720 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1