Advertisement
qwerty787788

OpenCup G

Dec 14th, 2014
250
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.68 KB | None | 0 0
  1. #include <cstring>
  2. #include <vector>
  3. #include <list>
  4. #include <map>
  5. #include <set>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20. #include <memory.h>
  21. #include <cassert>
  22.  
  23. using namespace std;
  24.  
  25. #define FILENAME "nanobugs"
  26.  
  27. int was[777][777];
  28. int where[777];
  29. vector <int> g[777];
  30.  
  31. int main() {
  32.   freopen(FILENAME ".in", "r", stdin);
  33.   freopen(FILENAME ".out", "w", stdout);
  34.   srand(8753);
  35.   int n, a, b;
  36.   scanf("%d %d %d", &n, &a, &b);
  37.   if (n % 2 == 1 && a == 1) {
  38.       printf("%d\n", -1);
  39.       return 0;                                                                
  40.   }
  41.   if (n % 2 == 1 && a == 2 && b == 1) {
  42.      int parts[8];
  43.      vector<int> gen;
  44.      for (int i = 0; i < n; i++) {
  45.        gen.push_back(0);
  46.      }
  47.      for (int i = 0; i < 7; i++) {
  48.        gen.push_back(1);
  49.      }
  50.      while (true) {
  51.        random_shuffle(gen.begin(), gen.end());
  52.        int cur = 0;
  53.        for (int i = 0; i < 8; i++) {
  54.          int sz = 0;
  55.          while (cur < (int) gen.size() && gen[cur] == 0) sz++, cur++;
  56.          parts[i] = sz;
  57.          cur++;
  58.        }      
  59.        bool ok = true;
  60.        for (int i = 0; i < 8; i++) {
  61.          if (parts[i] < 1) ok = false;
  62.        }
  63.        if (!ok) continue;
  64.        if (parts[0] + parts[2] + parts[6] == parts[1] + parts[3] + parts[7]) {
  65.          if (parts[0] + parts[2] + parts[4] == parts[1] + parts[3] + parts[5]) {
  66.            int part[n];
  67.            for (int j = 0; j < n; j++) {
  68.              int tmp = j;
  69.              part[j] = 0;
  70.              while (tmp >= parts[part[j]]) {
  71.                tmp -= parts[part[j]];
  72.                part[j]++;
  73.              }
  74.            }
  75.            cout << 2 << endl;
  76.            int msz = parts[0] + parts[2] + parts[6];
  77.            cout << msz << " ";
  78.            for (int j = 0; j < n; j++)
  79.              if (part[j] == 0 || part[j] == 2 || part[j] == 6) cout << (j + 1) << " ";
  80.            cout << "= ";
  81.            cout << msz << " ";
  82.            for (int j = 0; j < n; j++)
  83.              if (part[j] == 1 || part[j] == 3 || part[j] == 7) cout << (j + 1) << " ";
  84.            cout << endl;
  85.  
  86.            msz = parts[0] + parts[2] + parts[4];
  87.            cout << msz << " ";
  88.            for (int j = 0; j < n; j++)
  89.              if (part[j] == 0 || part[j] == 2 || part[j] == 4) cout << (j + 1) << " ";
  90.            cout << "= ";
  91.            cout << msz << " ";
  92.            for (int j = 0; j < n; j++)
  93.              if (part[j] == 1 || part[j] == 3 || part[j] == 5) cout << (j + 1) << " ";
  94.            cout << endl;
  95.            return 0;
  96.          }
  97.        }
  98.      }
  99.      return 0;
  100.   }
  101.   if (n % 4 == 3 && a == 4 && b == 3) {
  102.     cout << 4 << endl;
  103.     const int M = 5;
  104.     for (int i = 0; i < 3; i++)
  105.         for (int j = i + 1; j < 3; j++) {
  106.           cout << M << " ";
  107.           for (int k = 0; k < M; k++) {
  108.             cout << (i * M + k + 1) << " ";
  109.           }
  110.           cout << "^ ";
  111.           cout << M << " ";
  112.           for (int k = 0; k < M; k++) {
  113.             cout << (j * M + k + 1) << " ";
  114.           }
  115.           cout << endl;
  116.         }
  117.     int rem = n - M * 3;
  118.     cout << rem / 2 << " ";
  119.     for (int k = 0; k < rem / 2; k++) {
  120.       cout << (M * 3 + k + 1) << " ";
  121.     }
  122.     cout << "^ ";
  123.     cout << rem / 2 << " ";
  124.     for (int k = 0; k < rem / 2; k++) {
  125.       cout << (M * 3 + k + rem / 2 + 1) << " ";
  126.     }
  127.     cout << endl;
  128.     return 0;
  129.   }
  130.  
  131.   int ng = (n + a - 1) / a;
  132.   for (int i = 0; i < ng; i++) {
  133.     g[i].clear();
  134.     for (int j = 0; j < a; j++) {
  135.       g[i].push_back((i * a + j) % n);
  136.     }
  137.   }
  138.   vector < pair < vector <int>, vector <int> > > ret;
  139.   const int MAX = 1000;
  140.   int EVEN = MAX / 2;
  141.   int ODD = MAX / 2;
  142.   if (a == 1) {
  143.     EVEN = 0;
  144.     ODD = MAX;
  145.   }
  146.   for (int it = 0; it < EVEN; it++) {
  147.     for (int i = 0; i < n; i++) {
  148.       where[i] = 0;
  149.     }
  150.     for (int i = 0; i < n / a; i++) {
  151.       int cnt = rand() % (a / 2 + 1);
  152.       for (int j = 0; j < cnt; j++) {
  153.         for (int put = 1; put <= 2; put++) {
  154.           int x;
  155.           do {
  156.             x = rand() % a;
  157.           } while (where[i * a + x] != 0);
  158.           where[i * a + x] = put;
  159.         }
  160.       }
  161.     }
  162.     for (int i = n / a * a; i < n; i++) {
  163.       where[i] = 0;
  164.     }
  165.     if (n / a * a != n) {
  166.       int c1 = 0, c2 = 0;
  167.       for (int j = 0; j < a; j++) {
  168.         int w = g[ng - 1][j];
  169.         c1 += (where[w] == 1);
  170.         c2 += (where[w] == 2);
  171.       }
  172.       if (c1 != c2) {
  173.         it--;
  174.         continue;
  175.       }
  176.     }
  177.     vector <int> x;
  178.     vector <int> y;
  179.     for (int i = 0; i < n; i++) {
  180.       if (where[i] == 1) {
  181.         x.push_back(i + 1);
  182.       }
  183.       if (where[i] == 2) {
  184.         y.push_back(i + 1);
  185.       }
  186.     }
  187.     if (x.size() <= 1) {
  188.       it--;
  189.       continue;
  190.     }
  191.     ret.push_back(make_pair(x, y));
  192.   }
  193.   for (int it = 0; it < ODD; it++) {
  194.     for (int i = 0; i < n; i++) {
  195.       where[i] = 0;
  196.     }
  197.     for (int i = 0; i < n / a; i++) {
  198.       int cnt1, cnt2;
  199.       do {
  200.         cnt1 = rand() % (a + 1);
  201.         cnt2 = rand() % (a + 1);
  202.       } while (cnt1 == cnt2 || cnt1 + cnt2 > a);
  203.       for (int j = 0; j < cnt1; j++) {
  204.         int x;
  205.         do {
  206.           x = rand() % a;
  207.         } while (where[i * a + x] != 0);
  208.         where[i * a + x] = 1;
  209.       }
  210.       for (int j = 0; j < cnt2; j++) {
  211.         int x;
  212.         do {
  213.           x = rand() % a;
  214.         } while (where[i * a + x] != 0);
  215.         where[i * a + x] = 2;
  216.       }
  217.     }
  218.     for (int i = n / a * a; i < n; i++) {
  219.       where[i] = rand() % 2 + 1;
  220.     }
  221.     if (n / a * a != n) {
  222.       int c1 = 0, c2 = 0;
  223.       for (int j = 0; j < a; j++) {
  224.         int w = g[ng - 1][j];
  225.         c1 += (where[w] == 1);
  226.         c2 += (where[w] == 2);
  227.       }
  228.       if (c1 == c2) {
  229.         it--;
  230.         continue;
  231.       }
  232.     }
  233.     vector <int> x;
  234.     vector <int> y;
  235.     for (int i = 0; i < n; i++) {
  236.       if (where[i] == 1) {
  237.         x.push_back(i + 1);
  238.       }
  239.       if (where[i] == 2) {
  240.         y.push_back(i + 1);
  241.       }
  242.     }
  243.     if (x.size() <= 1 || x.size() != y.size()) {
  244.       it--;
  245.       continue;
  246.     }
  247.     ret.push_back(make_pair(x, y));
  248.   }
  249.   int rsz = ret.size();
  250.   printf("%d\n", rsz);
  251.   for (int i = 0; i < rsz; i++) {
  252.     int sz = ret[i].first.size();
  253.     printf("%d", sz);
  254.     for (int j = 0; j < sz; j++) {
  255.       printf(" %d", ret[i].first[j]);
  256.     }
  257.     printf(" %c ", i >= EVEN ? '^' : '=');
  258.     printf("%d", sz);
  259.     for (int j = 0; j < sz; j++) {
  260.       printf(" %d", ret[i].second[j]);
  261.     }
  262.     printf("\n");
  263.   }
  264.   return 0;
  265. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement