제출 #985124

#제출 시각아이디문제언어결과실행 시간메모리
985124Jawad_Akbar_JJ서열 (APIO23_sequence)C++17
28 / 100
2009 ms54016 KiB
#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; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...