Submission #985133

#	Time	Username	Problem	Language	Result	Execution time	Memory
985133		Jawad_Akbar_JJ	Sequence (APIO23_sequence)	C++17	28 / 100	1695 ms	57684 KiB

sequence

#include <iostream>
#include <vector>
#include <ctime>
#include <chrono>

using namespace std::chrono;

using namespace std;


struct node{
	node* bit[2];
	int cnt[2];
	int i;
	node(int b){
		i = b;
		bit[0] = bit[1] = NULL;
		cnt[0] = cnt[1] = 0;
	}
 
	void insert(int n){
		if (i==-1)
			return;
		bool b = (n&(1<<i));
		
		if (bit[b]==NULL)
			bit[b] = new node(i-1);
		
		cnt[b]++;
		bit[b]->insert(n);
	}
 
	int get(int k){
		if (i==-1)
			return 0;
		if (cnt[0]>=k)
			return bit[0]->get(k);
 
		k -= cnt[0];
		return (1<<i) + bit[1]->get(k);
	}

	void erase(int n){
		if (i==-1)
			return;
		bool b = (n&(1<<i));
		cnt[b]--;
		bit[b]->erase(n);
	}
	
};

int cnt[500005];

int opt2(int n,vector<int> v){
	
	node* root = new node(20);
	int ans = 0;
	
	auto start = high_resolution_clock::now();
		
	srand(time(0));
	int K = 1e7 / n;
	for (int k=0;;k++){
		int i = rand()%n;
		for (int j=i;j<n;j++)
			root->insert(v[j]),cnt[v[j]]++;
		for (int j=n-1;j>=i;j--){
			int k = j - i + 1;
			ans = max(ans,cnt[root->get((k + 1) / 2)]);
			if (k % 2 == 0)
				ans = max(ans,cnt[root->get(k / 2 + 1)]);
			root->erase(v[j]);
			cnt[v[j]]--;
		}
		auto stop = high_resolution_clock::now();
		auto duration = duration_cast<microseconds>(stop - start);

		int kk = duration.count() / 1000;
		if (kk >= 1500)
			break;
	}
	// cout<<"ans\n";
	return ans;
}

int sequence(int n,vector<int> v){

	if (n > 2000)
		return opt2(n,v);
	node* root = new node(20);
	int ans = 0;
	for (int i=0;i<n;i++){
		for (int j=i;j<n;j++)
			root->insert(v[j]),cnt[v[j]]++;
		for (int j=n-1;j>=i;j--){
			int k = j - i + 1;
			ans = max(ans,cnt[root->get((k + 1) / 2)]);
			if (k % 2 == 0)
				ans = max(ans,cnt[root->get(k / 2 + 1)]);
			root->erase(v[j]);
			cnt[v[j]]--;
		}
	}
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int opt2(int, std::vector<int>)':
sequence.cpp:63:6: warning: unused variable 'K' [-Wunused-variable]
   63 |  int K = 1e7 / n;
      |      ^

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18