• API
• FAQ
• Tools
• Archive
daily pastebin goal
60%
SHARE
TWEET

# Untitled

a guest Oct 12th, 2017 55 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
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.

Top