SHARE
TWEET

Untitled

a guest Dec 9th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <iomanip>
  11. #include <fstream>
  12. #include <cassert>
  13. #include <cstring>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <numeric>
  17. #include <ctime>
  18. #include <bitset>
  19. #include <complex>
  20. #include <random>
  21.  
  22. using namespace std;
  23.  
  24. bool check(int n, int k, vector<int> in, vector<int> pans) {
  25.     assert((int)in.size() == n);
  26.     assert((int)pans.size() == k);
  27.     assert(is_sorted(pans.begin(), pans.end()));
  28.     auto relax = [&](int &mn, int &wr, int i, int j) {
  29.         if (j < 0 || j >= k) {
  30.             return;
  31.         }
  32.         if (mn > abs(i - pans[j])) {
  33.             mn = abs(i - pans[j]);
  34.             wr = j;
  35.         }
  36.     };
  37.     int pnt = -1;
  38.     for (int i = 0; i < n; i++) {
  39.         if (in[i] != -1) {
  40.             while (pnt + 1 < k && pans[pnt + 1] < i) {
  41.                 pnt++;
  42.             }
  43.             int wr = -1;
  44.             int mn = n + 1;
  45.             relax(mn, wr, i, pnt);
  46.             relax(mn, wr, i, pnt + 1);
  47.             if (in[i] != wr) {
  48.                 return false;
  49.             }
  50.         }
  51.     }
  52.     return true;
  53. }
  54.  
  55. struct St {
  56.     vector<int> a;
  57.     vector<pair<int, int>> wr;
  58.  
  59.     int get_a(int x) {
  60.         return a[x];
  61.     }
  62.  
  63.     pair<int, int> get_wr(int x) {
  64.         return wr[x];
  65.     }
  66.  
  67.     void set(int l, int r, pair<int, int> x) {
  68.         for (int i = l; i <= r; i++) {
  69.             a[i] = 1;
  70.             wr[i] = x;
  71.         }
  72.     }
  73.  
  74.     void set_a(int i) {
  75.         a[i] = 1;
  76.     }
  77.  
  78.     St(int n) {
  79.         a.resize(n, 0);
  80.         wr.resize(n, {-1, -1});
  81.     }
  82.  
  83.     St(){}
  84. };
  85.  
  86. vector<int> solve(int n, int k, vector<int> in) {
  87.     const int K = 20;
  88.     vector<int> l(n);
  89.     vector<int> r(n);
  90.     l[0] = in[0];
  91.     for (int i = 1; i < n; i++) {
  92.         if (in[i] != -1) {
  93.             l[i] = in[i];
  94.         } else {
  95.             l[i] = l[i - 1];
  96.         }
  97.     }
  98.     r[n - 1] = in[n - 1];
  99.     for (int i = n - 2; i >= 0; i--) {
  100.         if (in[i] != -1) {
  101.             r[i] = in[i];
  102.         } else {
  103.             r[i] = r[i + 1];
  104.         }
  105.     }
  106.     auto find = [&](int i, int wr) {
  107.         if (wr == 0) {
  108.             return l[i];
  109.         } else {
  110.             return r[i];
  111.         }
  112.     };
  113.     vector<int> minp(k, -1);
  114.     vector<int> maxp(k, -1);
  115.     for (int i = 0; i < n; i++) {
  116.         if (in[i] != -1) {
  117.             if (minp[in[i]] == -1) {
  118.                 minp[in[i]] = i;
  119.             }
  120.             maxp[in[i]] = i;
  121.         }
  122.     }
  123.     auto check = [&](int i, int j, int k, int f, int s, int &ok) {
  124.         if (k < i || k > j) {
  125.             return;
  126.         }
  127.         if (abs(i - k) <= abs(j - k) && in[k] != f) {
  128.             ok = 0;
  129.         }
  130.         if (abs(i - k) > abs(j - k) && in[k] != s) {
  131.             ok = 0;
  132.         }
  133.     };
  134.     auto can_relax = [&](int i, int j, int iw, int jw) {
  135.         int f = find(i, iw);
  136.         int s = find(j, jw);
  137.         if (f == -1 || s == -1 || f + 1 != s) {
  138.             return 0;
  139.         }
  140.         int ok = 1;
  141.         check(i, j, maxp[f], f, s, ok);
  142.         check(i, j, minp[s], f, s, ok);
  143.         return ok;
  144.     };
  145.     vector<St> dp(2, St(n));
  146.     {
  147.         int fs = -1;
  148.         int ss = -1;
  149.         for (int i = 0; i < n; i++) {
  150.             if (in[i] == 0 && fs == -1) {
  151.                 fs = i;
  152.             }
  153.             if (in[i] == 1 && ss == -1) {
  154.                 ss = i;
  155.             }
  156.         }
  157.         for (int i = 0; i <= fs; i++) {
  158.             dp[1].set_a(i);
  159.         }
  160.         for (int i = fs; i < ss; i++) {
  161.             dp[0].set_a(i);
  162.         }
  163.     }
  164.     for (int i = 0; i < n; i++) {
  165.         for (int f = 0; f < 2; f++) {
  166.             if (!dp[f].get_a(i)) {
  167.                 continue;
  168.             }
  169.             for (int s = 0; s < 2; s++) {
  170.                 if (find(i, f) + 1 == k) {
  171.                     continue;
  172.                 }
  173.                 int omn = i + 1;
  174.                 if (i <= maxp[find(i, f)]) {
  175.                     int delta = maxp[find(i, f)] - i;
  176.                     omn = max(omn, i + 2 * delta);
  177.                 }
  178.                 if (!s) {
  179.                     omn = max(omn, minp[find(i, f) + 1]);
  180.                 }
  181.                 if (omn >= n || !can_relax(i, omn, f, s)) {
  182.                     continue;
  183.                 }      
  184.                 int omx = omn;     
  185.                 for (int j = K; j >= 0; j--) {
  186.                     if ((omx + (1 << j)) < n && can_relax(i, omx + (1 << j), f, s)) {
  187.                         omx += (1 << j);
  188.                     }
  189.                 }
  190.                 dp[s].set(omn, omx, {i, f});
  191.             }
  192.         }
  193.     }
  194.     vector<int> ans;
  195.     int toi = -1;
  196.     int toj = -1;
  197.     for (int i = n - 1; i >= 0; i--) {
  198.         for (int j = 0; j < 2; j++) {
  199.             if (dp[j].get_a(i) && find(i, j) == k - 1) {
  200.                 toi = i;
  201.                 toj = j;
  202.             }
  203.         }
  204.     }
  205.     assert(toi != -1);
  206.     while (toi != -1) {
  207.         ans.push_back(toi);
  208.         tie(toi, toj) = dp[toj].get_wr(toi);
  209.     }
  210.     reverse(ans.begin(), ans.end());
  211.     return ans;
  212. }
  213.  
  214. void read() {
  215.     int n, k;
  216.     cin >> n >> k;
  217.     vector<int> a(n);
  218.     for (auto &t : a) {
  219.         cin >> t;
  220.         t--;
  221.     }
  222.     auto rs = solve(n, k, a);
  223.     cout << "res:" << endl;
  224.     for (auto t : rs) {
  225.         cout << t + 1 << ' ';
  226.     }
  227.     cout << endl;
  228.     if (check(n, k, a, rs)) {
  229.         cout << "OK\n";
  230.     } else {
  231.         cout << "WA\n";
  232.     }
  233. }
  234.  
  235. void gen(int n, int k) {
  236.     set<int> sel;
  237.     while ((int)sel.size() < k) {
  238.         sel.insert(rand() % n);
  239.     }
  240.     vector<int> ps;
  241.     for (auto t : sel) {
  242.         ps.push_back(t);
  243.     }
  244.     vector<int> out(n, -1);
  245.     vector<int> cnt(k);
  246.     for (int i = 0; i < n; i++) {
  247.         int mn = n + 1;
  248.         int wr = -1;  
  249.         for (int j = 0; j < k; j++) {
  250.             if (mn > abs(i - ps[j])) {
  251.                 mn = abs(i - ps[j]);
  252.                 wr = j;
  253.             }
  254.         }  
  255.         out[i] = wr;
  256.         cnt[wr]++;
  257.     }
  258.     int sk = n / 2;
  259.     while (sk--) {
  260.         int i = rand() % n;
  261.         if (out[i] != -1 && cnt[out[i]] > 1) {
  262.             cnt[out[i]]--;
  263.             out[i] = -1;
  264.         }
  265.     }
  266.     {
  267.         cout << "Case:" << endl;
  268.         cout << n << ' ' << k << endl;
  269.         for (auto t : out) {
  270.             cout << t + 1 << ' ';
  271.          }
  272.          cout << endl;
  273.         auto rs = solve(n, k, out);
  274.         if (check(n, k, out, rs)) {
  275.             cout << "OK\n";
  276.         } else {
  277.             cout << "WA\n";
  278.             exit(0);
  279.         }
  280.         cout << endl;
  281.     }
  282. }
  283.  
  284. signed main() {
  285.     ios_base::sync_with_stdio(false);
  286.     cin.tie(0);
  287.    
  288.     // read();
  289.  
  290.     int n, k;
  291.     cin >> n >> k;
  292.     while (true) {
  293.         gen(n, k);
  294.     }
  295. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top