API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 12th, 2017
71
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.25 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. map < pair < int , int > , int > F;
  6. int n;
  7.  
  8. int recursive_dive(int stx,int sty,int x,int y,int n,int m) {
  9.  
  10.     if (x < stx || y < sty || x >= stx+(1<<n) || y >= sty+(1<<n)) return 0;
  11.  
  12.     if (n == m) {
  13.  
  14.         bool down = ( x >= stx+(1<<(n-1)) );
  15.         bool right = ( y >= sty+(1<<(n-1)) );
  16.  
  17.         if (down && right) return 3;
  18.         if (down) return 4;
  19.         if (right) return 2;
  20.         return 1;
  21.  
  22.     }
  23.  
  24.     n--;
  25.     int quart = 0;
  26.  
  27.     quart += recursive_dive(stx,sty,x,y,n,m);
  28.     quart += recursive_dive(stx+(1<<n),sty,x,y,n,m);
  29.     quart += recursive_dive(stx,sty+(1<<n),x,y,n,m);
  30.     quart += recursive_dive(stx+(1<<n),sty+(1<<n),x,y,n,m);
  31.  
  32.     return quart;
  33.  
  34. }
  35.  
  36. int get_quarter(int x,int y,int m) {
  37.  
  38.     return recursive_dive(0,0,x,y,n,m);
  39.  
  40. }
  41.  
  42. pair < int , int > recursive_dive_second(int stx,int sty,int x,int y,int n,int m) {
  43.  
  44.     if (x < stx || y < sty || x >= stx+(1<<n) || y >= sty+(1<<n)) return {-1,-1};
  45.  
  46.     if (n == m) return {stx,sty};
  47.  
  48.     n--;
  49.  
  50.     pair < int , int > start_point = {-1,-1};
  51.  
  52.     start_point = max ( start_point , recursive_dive_second(stx,sty,x,y,n,m) );
  53.     start_point = max ( start_point , recursive_dive_second(stx+(1<<n),sty,x,y,n,m) );
  54.     start_point = max ( start_point , recursive_dive_second(stx,sty+(1<<n),x,y,n,m) );
  55.     start_point = max ( start_point , recursive_dive_second(stx+(1<<n),sty+(1<<n),x,y,n,m) );
  56.  
  57.     return start_point;
  58. }
  59.  
  60. pair < int , int > get_start_coordinates(int x,int y,int m) {
  61.  
  62.     return recursive_dive_second(0,0,x,y,n,m);
  63.  
  64. }
  65.  
  66. bool check_for_forbidden(int stx,int sty,int enx,int eny) {
  67.  
  68.     for (int i = stx; i < enx; i++)
  69.         for (int j = sty; j < eny; j++)
  70.             if (!F[ {i,j} ]) return false;
  71.  
  72.     return true;
  73. }
  74.  
  75. vector < pair < int , int > > all_points;
  76.  
  77. bool all_is_clear(int stx,int sty,int enx,int eny) {
  78.  
  79.     for (auto P : all_points) {
  80.  
  81.         if (stx <= P.first && P.first < enx)
  82.             if (sty <= P.second && P.second < eny)
  83.                 return false;
  84.  
  85.     }
  86.  
  87.     return true;
  88.  
  89. }
  90.  
  91. bool dfs(int x,int y,int n,int dir,int &nextX,int &nextY) {
  92.  
  93.     if (F[ {x,y} ]) return false;
  94.  
  95.     nextX=x;
  96.     nextY=y;
  97.  
  98.     if (n == 0) {
  99.  
  100.         if (dir == 1) nextX--;
  101.         if (dir == 4) nextY--;
  102.         if (dir == 2) nextY++;
  103.         if (dir == 3) nextX++;
  104.         return true;
  105.  
  106.     }
  107.  
  108.     pair < int , int > start_point = get_start_coordinates(x,y,n);
  109.  
  110.     int stx = start_point.first,sty = start_point.second;
  111.  
  112.     if (n >= 1 && all_is_clear(stx,sty,stx+(1<<n),sty+(1<<n))) {
  113.  
  114.         x-=stx;
  115.         y-=sty;
  116.  
  117.         x=(1<<n)-x-1;
  118.  
  119.         if (dir == 1 && x == 0)
  120.             goto next_step;
  121.         if (dir == 2 && y == (1<<n)-1)
  122.             goto next_step;
  123.         if (dir == 3 && x == (1<<n)-1)
  124.             goto next_step;
  125.         if (dir == 4 && y == 0)
  126.             goto next_step;
  127.  
  128.         x=(1<<n)-x-1;
  129.         y=(1<<n)-y-1;
  130.  
  131.         if (dir == 1 && x == 0)
  132.             goto next_step;
  133.         if (dir == 2 && y == (1<<n)-1)
  134.             goto next_step;
  135.         if (dir == 3 && x == (1<<n)-1)
  136.             goto next_step;
  137.         if (dir == 4 && y == 0)
  138.             goto next_step;
  139.  
  140.         y=(1<<n)-y-1;
  141.         swap(x,y);
  142.         x=(1<<n)-x-1;
  143.  
  144.         if (dir == 1 && x == 0)
  145.             goto next_step;
  146.         if (dir == 2 && y == (1<<n)-1)
  147.             goto next_step;
  148.         if (dir == 3 && x == (1<<n)-1)
  149.             goto next_step;
  150.         if (dir == 4 && y == 0)
  151.             goto next_step;
  152.  
  153.         x=(1<<n)-x-1;
  154.         y=(1<<n)-y-1;
  155.  
  156.         next_step :
  157.  
  158.         nextX=x+stx;
  159.         nextY=y+sty;
  160.  
  161.         if (dir == 1) nextX--;
  162.         if (dir == 4) nextY--;
  163.         if (dir == 2) nextY++;
  164.         if (dir == 3) nextX++;
  165.  
  166.         return true;
  167.  
  168.     }
  169.  
  170.     vector < int > directions;
  171.     int quart = get_quarter(x,y,n);
  172.  
  173.     if (quart == 1) {
  174.  
  175.         if (dir == 1)
  176.             directions = {3,2,1,1};
  177.         if (dir == 2)
  178.             directions = {3,2,1,2};
  179.         if (dir == 3)
  180.             directions = {2,3,4,3};
  181.         if (dir == 4)
  182.             directions = {2,3,4,4};
  183.  
  184.     }
  185.  
  186.     if (quart == 2) {
  187.  
  188.         if (dir == 1)
  189.             directions = {3,4,1,1};
  190.         if (dir == 2)
  191.             directions = {4,3,2,2};
  192.         if (dir == 3)
  193.             directions = {4,3,2,3};
  194.         if (dir == 4)
  195.             directions = {3,4,1,4};
  196.  
  197.     }
  198.  
  199.     if (quart == 4) {
  200.  
  201.         if (dir == 1)
  202.             directions = {2,1,4,1};
  203.         if (dir == 2)
  204.             directions = {1,2,3,2};
  205.         if (dir == 3)
  206.             directions = {1,2,3,3};
  207.         if (dir == 4)
  208.             directions = {2,1,4,4};
  209.  
  210.     }
  211.  
  212.     if (quart == 3) {
  213.  
  214.         if (dir == 1)
  215.             directions = {4,1,2,1};
  216.         if (dir == 2)
  217.             directions = {4,1,2,2};
  218.         if (dir == 3)
  219.             directions = {1,4,3,3};
  220.         if (dir == 4)
  221.             directions = {1,4,3,4};
  222.  
  223.     }
  224.  
  225.     bool quarter;
  226.     quarter = true;
  227.  
  228.     if (n <= 3) {
  229.  
  230.         pair < int , int > start_point = get_start_coordinates(x,y,n);
  231.  
  232.         int stx = start_point.first,sty = start_point.second;
  233.  
  234.         bool forbidden1 = check_for_forbidden(stx,sty,stx+(1<<(n-1)),sty+(1<<(n-1)));
  235.         bool forbidden2 = check_for_forbidden(stx,sty+(1<<(n-1)),stx+(1<<(n-1)),sty+(1<<n));
  236.         bool forbidden3 = check_for_forbidden(stx+(1<<(n-1)),sty+(1<<(n-1)),stx+(1<<n),sty+(1<<n));
  237.         bool forbidden4 = check_for_forbidden(stx+(1<<(n-1)),sty,stx+(1<<n),sty+(1<<(n-1)));
  238.  
  239.         if (!forbidden1 && !forbidden2 && !forbidden3 && !forbidden4)
  240.             goto normal_solution;
  241.  
  242.         if (quart == 1) {
  243.  
  244.             if (forbidden2 && forbidden4 && forbidden3) {
  245.  
  246.                 if (dir == 2 || dir == 3)
  247.                     return false;
  248.                 directions = {dir};
  249.                 goto normal_solution;
  250.  
  251.             }
  252.  
  253.             if (forbidden2 && forbidden4)
  254.                 return false;
  255.  
  256.             if (forbidden2 && forbidden3) {
  257.  
  258.                 if (dir == 1 || dir == 2)
  259.                     return false;
  260.                 directions = {3,dir};
  261.                 goto normal_solution;
  262.  
  263.             }
  264.  
  265.             if (forbidden2) {
  266.  
  267.                 if (dir == 1 || dir == 4)
  268.                     return false;
  269.                 directions = {3,2,dir};
  270.                 goto normal_solution;
  271.  
  272.             }
  273.  
  274.             if (forbidden3 && forbidden4) {
  275.  
  276.                 if (dir == 3 || dir == 4)
  277.                     return false;
  278.                 directions = {2,dir};
  279.                 goto normal_solution;
  280.  
  281.             }
  282.  
  283.             if (forbidden3)
  284.                 return false;
  285.  
  286.             if (dir == 1 || dir == 4)
  287.                 return false;
  288.             directions = {2,3,dir};
  289.             goto normal_solution;
  290.  
  291.         }
  292.  
  293.         if (quart == 2) {
  294.  
  295.             if (forbidden1 && forbidden4 && forbidden3) {
  296.  
  297.                 if (dir == 3 || dir == 4)
  298.                     return false;
  299.                 directions = {dir};
  300.                 goto normal_solution;
  301.  
  302.             }
  303.  
  304.             if (forbidden1 && forbidden3)
  305.                 return false;
  306.  
  307.             if (forbidden1 && forbidden4) {
  308.  
  309.                 if (dir == 1 || dir == 4)
  310.                     return false;
  311.                 directions = {3,dir};
  312.                 goto normal_solution;
  313.  
  314.             }
  315.  
  316.             if (forbidden1) {
  317.  
  318.                 if (dir == 1 || dir == 2)
  319.                     return false;
  320.                 directions = {3,4,dir};
  321.                 goto normal_solution;
  322.  
  323.             }
  324.  
  325.             if (forbidden3 && forbidden4) {
  326.  
  327.                 if (dir == 3 || dir == 2)
  328.                     return false;
  329.                 directions = {4,dir};
  330.                 goto normal_solution;
  331.  
  332.             }
  333.  
  334.             if (forbidden4)
  335.                 return false;
  336.  
  337.             if (dir == 1 || dir == 2)
  338.                 return false;
  339.             directions = {4,3,dir};
  340.             goto normal_solution;
  341.  
  342.         }
  343.  
  344.         if (quart == 3) {
  345.  
  346.             if (forbidden2 && forbidden4 && forbidden1) {
  347.  
  348.                 if (dir == 1 || dir == 4)
  349.                     return false;
  350.                 directions = {dir};
  351.                 goto normal_solution;
  352.  
  353.             }
  354.  
  355.             if (forbidden2 && forbidden4)
  356.                 return false;
  357.  
  358.             if (forbidden4 && forbidden1) {
  359.  
  360.                 if (dir == 4 || dir == 3)
  361.                     return false;
  362.                 directions = {1,dir};
  363.                 goto normal_solution;
  364.  
  365.             }
  366.  
  367.             if (forbidden4) {
  368.  
  369.                 if (dir == 3 || dir == 2)
  370.                     return false;
  371.                 directions = {1,4,dir};
  372.                 goto normal_solution;
  373.  
  374.             }
  375.  
  376.             if (forbidden1 && forbidden2) {
  377.  
  378.                 if (dir == 1 || dir == 2)
  379.                     return false;
  380.                 directions = {4,dir};
  381.                 goto normal_solution;
  382.  
  383.             }
  384.  
  385.             if (forbidden1)
  386.                 return false;
  387.  
  388.             if (dir == 3 || dir == 2)
  389.                 return false;
  390.             directions = {4,1,dir};
  391.             goto normal_solution;
  392.  
  393.         }
  394.  
  395.         if (quart == 4) {
  396.  
  397.             if (forbidden1 && forbidden2 && forbidden3) {
  398.  
  399.                 if (dir == 1 || dir == 2)
  400.                     return false;
  401.                 directions = {dir};
  402.                 goto normal_solution;
  403.  
  404.             }
  405.  
  406.             if (forbidden1 && forbidden3)
  407.                 return false;
  408.  
  409.             if (forbidden3 && forbidden2) {
  410.  
  411.                 if (dir == 2 || dir == 3)
  412.                     return false;
  413.                 directions = {1,dir};
  414.                 goto normal_solution;
  415.  
  416.             }
  417.  
  418.             if (forbidden3) {
  419.  
  420.                 if (dir == 3 || dir == 4)
  421.                     return false;
  422.                 directions = {1,2,dir};
  423.                 goto normal_solution;
  424.  
  425.             }
  426.  
  427.             if (forbidden1 && forbidden2) {
  428.  
  429.                 if (dir == 1 || dir == 4)
  430.                     return false;
  431.                 directions = {2,dir};
  432.                 goto normal_solution;
  433.  
  434.             }
  435.  
  436.             if (forbidden2)
  437.                 return false;
  438.  
  439.             if (dir == 3 || dir == 4)
  440.                 return false;
  441.             directions = {2,1,dir};
  442.             goto normal_solution;
  443.  
  444.         }
  445.  
  446.     }
  447.  
  448.     normal_solution :
  449.  
  450.     for (auto direction : directions) {
  451.  
  452.         quarter &= dfs(nextX,nextY,n-1,direction,nextX,nextY);
  453.         if (!quarter)
  454.             break;
  455.  
  456.     }
  457.  
  458.     return quarter;
  459.  
  460. }
  461.  
  462. int main() {
  463.  
  464.     //freopen("sample.in","r",stdin);
  465.  
  466.     int num_points;
  467.  
  468.     cin >> n >> num_points;
  469.  
  470.     for (int i = 1; i <= num_points; i++) {
  471.  
  472.         int a,b;
  473.         cin >> a >> b;
  474.         F[ {a,b} ]=1;
  475.         all_points.push_back( {a,b} );
  476.  
  477.     }
  478.  
  479.     for (int i = 1; i <= 4; i++) {
  480.  
  481.         int nextX = 0,nextY = 0;
  482.  
  483.         if (dfs(0,0,n,i,nextX,nextY)) {
  484.  
  485.             if (nextX < 0) nextX++;
  486.             if (nextX >= (1<<n)) nextX--;
  487.             if (nextY < 0) nextY++;
  488.             if (nextY >= (1<<n)) nextY--;
  489.  
  490.             cout << nextX << " " << nextY << endl;
  491.  
  492.         } else {
  493.  
  494.             cout << "NIE" << endl;
  495.  
  496.         }
  497.  
  498.     }
  499. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!