daily pastebin goal
17%
SHARE
TWEET

Untitled

a guest Oct 12th, 2017 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
Top