Guest User

Untitled

a guest
Oct 12th, 2014
262
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <map>
  4. #include <math.h>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <cstdio>
  8. #include <set>
  9. #include <queue>
  10. #include <sstream>
  11. #include <deque>
  12. #include <memory.h>
  13. #include <cassert>
  14. #include <ctime>
  15. #include <cstring>
  16. #include <cstdlib>
  17.  
  18. using namespace std;
  19.  
  20. #define ll long long
  21. #pragma comment(linker, "/STACK:64000000")
  22.  
  23. const int maxn = 200200;
  24. const int inf = 1000000007;
  25. const int mod = 1000000007;
  26. const int dx[4] = {1, -1, 0, 0};
  27. const int dy[4] = {0, 0, 1, -1};
  28.  
  29. int n;
  30. int a[maxn], p[maxn];
  31. bool used[maxn];
  32.  
  33. void check() {
  34.     vector<vector<int> > b(n + 2, vector<int>());
  35.     for (int i = 1; i <= 2 * n; i++) {
  36.         b[a[i]].push_back(i);
  37.     }
  38.     int cnt = 0;
  39.     for (int i = 1; i <= n + 1; i++) {
  40.         cnt += b[i].size() == 2 && b[i][1] - b[i][0] == i;
  41.     }
  42.     assert(cnt == n);
  43. }
  44.  
  45. bool rec(int cur, int frst) {
  46.     if (cur == n) {
  47.         if (n == 0) {
  48.             cout << "\"\", ";
  49.             return 1;
  50.         }
  51.         cout << "\"";
  52.         for (int i = 1; i <= 2 * n; i++) {
  53.             cout << a[i];
  54.             if (i == 2 * n) cout << "\", ";
  55.             else cout << " ";
  56.         }  
  57.         check();
  58.         return 1;
  59.     }
  60.     while (a[frst] != -1) frst++;
  61.     for (int i = n + 1; i >= 1; i--) {
  62.         if (!used[i] && frst + i <= 2 * n && a[frst + i] == -1) {
  63.             used[i] = 1;
  64.             a[frst] = a[frst + i] = i;
  65.             if (rec(cur + 1, frst + 1)) return 1;
  66.             a[frst] = a[frst + i] = -1;        
  67.             used[i] = 0;
  68.         }
  69.     }
  70.     return 0;
  71. }
  72.  
  73. void generateAnswers() {
  74.     cout << "const string ans[] = {";
  75.     for (n = 0; n <= 100; n++) {
  76.         memset(used, 0, sizeof(used));
  77.         memset(a, -1, sizeof(a));
  78.         if (!rec(0, 1)) {
  79.             cout << "\"-1\", " << endl;
  80.         }
  81.     }
  82. }
  83.  
  84.  
  85. int main() {
  86.     freopen("sequence.in", "r", stdin);
  87.     freopen("sequence.out", "w", stdout);
  88.     ios_base::sync_with_stdio(0);
  89.  
  90.     generateAnswers();
  91.  
  92.     /*int n;
  93.     cin >> n;
  94.     cout << ans[n] << endl; */
  95.  
  96.     return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment