fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXA = 10005;   // tool id <= 10000
  5. const int MAXK = 20005;   // k <= 20000
  6. const int MAXN = 1005;    // n <= 1000
  7.  
  8. int n, k;
  9. int a[MAXK], nxt[MAXK];
  10. int cur[MAXA];
  11. long long ans = 0;
  12.  
  13. struct cmp {
  14.     bool operator()(int x, int y) const {
  15.         return cur[x] > cur[y];
  16.     }
  17. };
  18.  
  19. priority_queue<int, vector<int>, cmp> g[MAXN]; // g[1..n]
  20.  
  21. void nhan(int i, int x){
  22.     if (i <= 0) return;
  23.     auto &q = g[i];
  24.     if ((int)q.size() == 2){
  25.         int y = q.top(); q.pop();
  26.         ++ans;               // move y down one level
  27.         nhan(i-1, y);
  28.     }
  29.     q.push(x);
  30. }
  31.  
  32. void doi(int i, int x){
  33.     if (i <= 0) return;
  34.     auto &q = g[i];
  35.     bool ok = false;
  36.     if (!q.empty()){
  37.         if (q.top() == x) ok = true;
  38.         else{
  39.             int tmp = q.top(); q.pop();
  40.             if (!q.empty() && q.top() == x) ok = true;
  41.             q.push(tmp);
  42.         }
  43.     }
  44.     if (ok) return;
  45.     if ((int)q.size() == 2){
  46.         int y = q.top(); q.pop();
  47.         ++ans;               // move y down one level
  48.         nhan(i-1, y);
  49.     }
  50.     doi(i-1, x);
  51. }
  52.  
  53. int main(){
  54.     ios::sync_with_stdio(false);
  55.     cin.tie(nullptr);
  56.     if (!(cin >> n >> k)) return 0;
  57.     for (int i = 1; i <= k; ++i) cin >> a[i];
  58.     // init cur: no next occurrence => k+1
  59.     for (int v = 0; v < MAXA; ++v) cur[v] = k + 1;
  60.     // compute nxt[i] (next occurrence index) by scanning backwards
  61.     for (int i = k; i >= 1; --i){
  62.         nxt[i] = cur[a[i]];
  63.         cur[a[i]] = i;
  64.     }
  65.     // process sequence: for each i, try to ensure a[i] at level n, then update cur[a[i]] = nxt[i]
  66.     for (int i = 1; i <= k; ++i){
  67.         doi(n, a[i]);
  68.         cur[a[i]] = nxt[i];
  69.     }
  70.     cout << ans * 2 << '\n';
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3 12
1 2 3 2 1 4 2 1 1 2 1 3
stdout
copy 
0
https://ideone.com/cDKrEr
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!