Submission #985124

#	Time	Username	Problem	Language	Result	Execution time	Memory
985124		Jawad_Akbar_JJ	Sequence (APIO23_sequence)	C++17	28 / 100	2009 ms	54016 KiB

sequence

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

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;
	srand(time(0));
	int K = 1e7 / n;
	for (int k=0;k<K;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]]--;
		}
	}
	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;
}

// int main(){
// 	int n;
// 	cin>>n;

// 	vector<int> v(n);

// 	for (int i=1;i<=n;i++)
// 		cin>>v[i-1];
// 	cout<<sequence(n,v)<<endl;
// }

• 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