fork download 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll int
  4. #define el "\n"
  5. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define __ROOT__ int main()
  7. #pragma GCC optimize("O2")
  8. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  9. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  10. #define compare(v) sort((v).begin(), (v).end()), (v).erase(unique((v).begin(), (v).end()), (v).end());
  11. using namespace std;
  12.  
  13. const int LOG = 30;
  14. const int MAXN = 1000001;
  15.  
  16. ll n, k;
  17. ll arr[MAXN];
  18.  
  19. struct Node {
  20.     Node *child[2];
  21.     ll cnt, exit;
  22.     Node() {
  23.         child[0] = child[1] = nullptr;
  24.         cnt = exit = 0;
  25.     }
  26. };
  27. Node *root;
  28.  
  29. void add(ll x) {
  30.     Node *p = root;
  31.     FORD(i, LOG, 0) {
  32.         ll t = (x >> i) & 1;
  33.         if(p->child[t] == nullptr) p->child[t] = new Node();
  34.         p = p->child[t];
  35.         p->cnt++;
  36.     }
  37.     p->exit++;
  38. }
  39.  
  40. void del(ll x) {
  41.     Node *p = root;
  42.     FORD(i, LOG, 0) {
  43.         ll t = (x >> i) & 1;
  44.         if(p->child[t] == nullptr) return; // không có gì để xóa
  45.         p = p->child[t];
  46.         p->cnt--;
  47.     }
  48.     p->exit--;
  49. }
  50.  
  51. ll query_k(ll k) { // tìm phần tử nhỏ thứ k
  52.     ll res = 0;
  53.     Node *p = root;
  54.     FORD(i, LOG, 0) {
  55.         if(!p) break;
  56.         ll leftt = p->child[0] ? p->child[0]->cnt : 0;
  57.         if(k > leftt) {
  58.             k -= leftt;
  59.             res |= (1 << i);
  60.             p = p->child[1];
  61.         } else {
  62.             p = p->child[0];
  63.         }
  64.     }
  65.     return res;
  66. }
  67.  
  68. void init() {
  69.     cin >> n >> k;
  70.     FOR(i,1,n) cin >> arr[i];
  71. }
  72.  
  73. vector<ll> res;
  74.  
  75. void solve() {
  76.     FOR(len, k, n) {
  77.         if(len % 2 == 0) continue;
  78.         root = new Node(); 
  79.         ll l = 1;
  80.         FOR(i, 1, n) {
  81.             add(arr[i]);
  82.             while(i - l + 1 > len) del(arr[l++]);
  83.             if(i - l + 1 == len)
  84.                 res.push_back(query_k(len/2 + 1));
  85.         }
  86.     }
  87.     compare(res);
  88.     cout << res.size() << el;
  89.     for(ll v: res) cout << v << " ";
  90. }
  91.  
  92. __ROOT__ {
  93.     fast;
  94.     int t = 1; // cin >> t;
  95.     while(t--) {
  96.         init();
  97.         solve();
  98.     }
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/MiM8ld
language:
C++ 4.3.2 (gcc-4.3.2)
created:
17 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!