API tools faq
paste
Advertisement
Guest User

Codeforces Marathon

a guest
Apr 4th, 2012
319
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 29.05 KB | None | 0 0
raw download clone embed print report
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #include <algorithm>
  3. #include <string>
  4. #include <set>
  5. #include <map>
  6. #include <vector>
  7. #include <queue>
  8. #include <iostream>
  9. #include <iterator>
  10. #include <cmath>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <sstream>
  14. #include <fstream>
  15. #include <ctime>
  16. #include <cstring>
  17. //#include <unordered_set>
  18. #pragma comment(linker, "/STACK:66777216")
  19. using namespace std;
  20. #define pb push_back
  21. #define ppb pop_back
  22. #define pi 3.1415926535897932384626433832795028841971
  23. #define mp make_pair
  24. #define x first
  25. #define y second
  26. #define aapii pair<int,int>
  27. #define pdd pair<double,double>
  28. #define INF 1000000000
  29. #define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
  30. #define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
  31. #define all(c) (c).begin(), (c).end()
  32. #define SORT(c) sort(all(c))
  33. #define rep(i,n) FOR(i,1,(n))
  34. #define rept(i,n) FOR(i,0,(n)-1)
  35. #define L(s) (int)((s).size())
  36. #define C(a) memset((a),0,sizeof(a))
  37. #define VI vector <int>
  38. #define ll long long
  39. #define TIME_LIMIT 3.85
  40.  
  41. struct pii {
  42.     int x, y;
  43.     pii() : x(0), y(0) {}
  44.     pii(int _x, int _y) : x(_x), y(_y) {}
  45. };
  46. inline bool operator <(const pii &a, const pii &b) {
  47.     if (a.x != b.x) return a.x < b.x; else
  48.         return a.y < b.y;
  49. }
  50. inline bool operator ==(const pii &a, const pii &b) {
  51.     return a.x == b.x && a.y == b.y;
  52. }
  53.  
  54. double getTime() {
  55. #ifndef LOCAL
  56.     unsigned long long time;
  57.     __asm__ volatile ("rdtsc" : "=A" (time));
  58. #ifndef ONLINE_JUDGE
  59.     return time / 2.53e9;
  60. #else
  61.     return time / 2.66e9;
  62. #endif
  63. #else
  64.     return 1.0 * clock() / CLOCKS_PER_SEC;
  65. #endif
  66. }
  67. int a,b,c,d,i,j,n,m,k,w,h,ans, ssize, updated_ans;
  68. double startTime, lastStart;
  69. //vector<pii> scaled[101];
  70. pii scaled[101][1001];
  71. int len[101];
  72. int pr[201], st[201];
  73. pii cur[204];
  74. pii cord[101], best[101];
  75. pair<pii, pii> rcord[101];
  76. int nomsq[101];
  77. int ax[102], ay[102], nscale[102], orient[102];
  78. int bax[102], bay[102], bnscale[102], borient[102];
  79. int mem[102];
  80. int opt, bopt;
  81. bool used[101];
  82. bool RN, SW;
  83.  
  84. inline void insert(int &k, int pos, pii val) {
  85.     FORD(i, k, pos + 1) cur[i] = cur[i - 1];
  86.     cur[pos] = val;
  87.     ++k;
  88. }
  89. inline void erase(int &k, int pos) {
  90.     FOR(i, pos, k - 2) {
  91.         cur[i] = cur[i + 1];
  92.     }
  93.     --k;
  94. }
  95. inline void normalize(int &k) {
  96.     while (1) {
  97.         bool ok = 1;
  98.         for (int i = 1; i < k - 1;) {
  99.             if ((cur[i].x == cur[i - 1].x && cur[i].x == cur[i + 1].x) || (cur[i].y == cur[i - 1].y && cur[i].y == cur[i + 1].y)) {
  100.                 erase(k, i);
  101.                 continue;
  102.             }
  103.             ++i;
  104.         }
  105.         if (ok) break;
  106.     }
  107. }
  108. int T = 0, CC = 0;
  109. char buf[101];
  110. inline char* toDouble(int a) {
  111.     char *res = buf;
  112.     if (a < 0) {
  113.         *(res++) = '-';
  114.         a = -a;
  115.     }
  116.     sprintf(res, "%d.%d", a / 10, a % 10);
  117.     return res;
  118. }
  119.  
  120. inline int getS(int v);
  121. inline pair<pii, pii> getCoord(int v);
  122. inline int markBad(int v) {
  123.     pair<pii, pii> t1 = getCoord(v);
  124.     int s = 0, num = -1;
  125.     rept(i, ssize) {
  126.         int w = st[i];
  127.         if (!used[w]) continue;
  128.         pair<pii, pii> t2 = rcord[w];
  129.         int x1 = max(t1.x.x, t2.x.x);
  130.         int y1 = max(t1.x.y, t2.x.y);
  131.         int x2 = min(t1.y.x, t2.y.x);
  132.         int y2 = min(t1.y.y, t2.y.y);
  133.         if (x2 > x1 && y2 > y1) {
  134.             num = w;
  135.             ++s;
  136.         }
  137.     }
  138.     if (s > 1) return -1; else
  139.         if (s == 0) return -2; else
  140.             return num;
  141. }
  142. inline void refresh() {
  143.     memcpy(borient, orient, sizeof(borient));
  144.     memcpy(best, cord, sizeof(best));
  145.     memcpy(bax, ax, sizeof(bax));
  146.     memcpy(bay, ay, sizeof(bay));
  147.     memcpy(bnscale, nscale, sizeof(bnscale));
  148. }
  149. inline bool nudge() {
  150.     memcpy(orient, borient, sizeof(borient));
  151.     memcpy(cord, best, sizeof(best));
  152.     memcpy(ax, bax, sizeof(bax));
  153.     memcpy(ay, bay, sizeof(bay));
  154.     memcpy(nscale, bnscale, sizeof(bnscale));
  155.     opt = bopt;
  156.     ssize = 0;
  157.     VI xs, ys;
  158.     rept(i, n) {
  159.         if (best[i].x == -1) used[i] = 0; else
  160.             used[i] = 1;
  161.         rcord[i] = getCoord(i);
  162.         if (used[i]) {
  163.             st[ssize++] = i;
  164.             xs.pb(rcord[i].x.x);
  165.             xs.pb(rcord[i].y.x);
  166.             //xs.pb(rcord[i].x.x + ax[i]);
  167.             //xs.pb(rcord[i].y.x + ax[i]);
  168.  
  169.             ys.pb(rcord[i].x.y);
  170.             ys.pb(rcord[i].y.y);
  171.             //ys.pb(rcord[i].x.y + ay[i]);
  172.             //ys.pb(rcord[i].y.y + ay[i]);
  173.         }
  174.     }
  175.     rept(i, n) {
  176.         if (used[i]) mem[i] = getS(i);
  177.     }
  178.  
  179.     //cerr << rcord[3].x.x << " " << rcord[3].x.y << endl;
  180.  
  181.     SORT(xs); xs.resize(unique(all(xs)) - xs.begin());
  182.     SORT(ys); ys.resize(unique(all(ys)) - ys.begin());
  183.  
  184.     random_shuffle(all(xs));
  185.     if (L(xs) > 20) xs.resize(20);
  186.     random_shuffle(all(ys));
  187.     if (L(ys) > 20) ys.resize(20);
  188.  
  189.     int nadd = -1;
  190.     pair<pii, pii> wt;
  191.     int beg = ans;
  192.     bool stop = 0;
  193.     rept(i, L(xs)) {
  194.         int x = xs[i];
  195.         rept(j, L(ys)) {
  196.             int y = ys[j];
  197.             if (getTime() - startTime > 4.85) {
  198.                 stop = 1;
  199.                 break;
  200.             }
  201.  
  202.             rept(i, n) {
  203.                 if (!used[i]) continue;
  204.  
  205.                 rept(j, len[i]) {
  206.                     int cw = scaled[i][j].x, ch = scaled[i][j].y;
  207.                     if (ans - mem[i] + 2 * cw + 2 * ch <= ans) continue;
  208.                     int now = 1, cnt = 0;
  209.                     rept(z, 2) {
  210.                         if (z == 1) {
  211.                             swap(cw, ch);
  212.                             now *= -1;
  213.                         }
  214.                         if (x + cw > w || y + ch > h) {
  215.                             ++cnt;
  216.                             continue;
  217.                         }
  218.  
  219.                         cord[i] = pii(x, y);
  220.                         rcord[i] = mp(pii(x, y), pii(x + cw, y + ch));
  221.                         nscale[i] = j;
  222.                         ax[i] = ay[i] = 0;
  223.                         orient[i] = now;
  224.                         int t = getS(i);
  225.                         int ns = ans - mem[i] + t;
  226.                         //cerr << ns << " " << beg << endl;
  227.  
  228.                         if (ns > ans) {
  229.                             ans = ns;
  230.                             best[i] = cord[i];
  231.                             bnscale[i] = nscale[i];
  232.                             bax[i] = ax[i];
  233.                             bay[i] = bax[i];
  234.                             borient[i] = orient[i];
  235.                             rept(l, n) mem[l] = getS(l);
  236.                             //nadd = i;
  237.                             //wt = mp(pii(x, y), pii(j, now));
  238.                         } else {
  239.                             cord[i] = best[i];
  240.                             nscale[i] = bnscale[i];
  241.                             ax[i] = bax[i];
  242.                             ay[i] = bay[i];
  243.                             orient[i] = borient[i];
  244.                             rcord[i] = getCoord(i);
  245.                         }
  246.                     }
  247.                     if (cnt == 2) break;
  248.                 }
  249.             }
  250.         }
  251.         if (stop) break;
  252.     }
  253.  
  254.     /*if (nadd != -1) {
  255.     used[nadd] = 1;
  256.     cord[nadd] = wt.x;
  257.     nscale[nadd] = wt.y.x;
  258.     orient[nadd] = wt.y.y;
  259.     ax[nadd] = ay[nadd] = 0;
  260.     rept(l, n) if (!used[l]) cord[l] = pii(-1, -1);
  261.     refresh();
  262.     }*/
  263.  
  264.     if (ans == beg) return 0; else
  265.         return 1;
  266. }
  267. inline bool nudge2() {
  268.     memcpy(orient, borient, sizeof(borient));
  269.     memcpy(cord, best, sizeof(best));
  270.     memcpy(ax, bax, sizeof(bax));
  271.     memcpy(ay, bay, sizeof(bay));
  272.     memcpy(nscale, bnscale, sizeof(bnscale));
  273.     opt = bopt;
  274.     ssize = 0;
  275.     VI xs, ys;
  276.     rept(i, n) {
  277.         if (best[i].x == -1) used[i] = 0; else
  278.             used[i] = 1;
  279.         rcord[i] = getCoord(i);
  280.         if (used[i]) {
  281.             st[ssize++] = i;
  282.             xs.pb(rcord[i].x.x);
  283.             xs.pb(rcord[i].y.x);
  284.             //xs.pb(rcord[i].x.x + ax[i]);
  285.             //xs.pb(rcord[i].y.x + ax[i]);
  286.  
  287.             ys.pb(rcord[i].x.y);
  288.             ys.pb(rcord[i].y.y);
  289.             //ys.pb(rcord[i].x.y + ay[i]);
  290.             //ys.pb(rcord[i].y.y + ay[i]);
  291.         }
  292.     }
  293.     rept(i, n) {
  294.         if (used[i]) mem[i] = getS(i);
  295.     }
  296.  
  297.     SORT(xs); xs.resize(unique(all(xs)) - xs.begin());
  298.     SORT(ys); ys.resize(unique(all(ys)) - ys.begin());
  299.  
  300.     random_shuffle(all(xs));
  301.     if (L(xs) > 20) xs.resize(20);
  302.     random_shuffle(all(ys));
  303.     if (L(ys) > 20) ys.resize(20);
  304.  
  305.     int nt = -1, nadd = -1;
  306.     pair<pii, pii> wt;
  307.     int beg = ans;
  308.     bool stop = 0;
  309.     rept(ii, L(xs)) {
  310.         int x = xs[ii];
  311.         rept(jj, L(ys)) {
  312.             int y = ys[jj];
  313.             if (getTime() - startTime > 4.85) {
  314.                 stop = 1;
  315.                 break;
  316.             }
  317.  
  318.             rept(i, n) {
  319.                 if (used[i]) continue;
  320.                 rept(j, len[i]) {
  321.                     int cw = scaled[i][j].x, ch = scaled[i][j].y;
  322.                     if (beg + 2 * cw + 2 * ch <= ans) continue;
  323.                     int now = 1, cnt = 0;
  324.                     rept(z, 2) {
  325.                         if (z == 1) {
  326.                             swap(cw, ch);
  327.                             now *= -1;
  328.                         }
  329.                         if (x + cw > w || y + ch > h) {
  330.                             ++cnt;
  331.                             continue;
  332.                         }
  333.  
  334.                         cord[i] = pii(x, y);
  335.                         rcord[i] = mp(pii(x, y), pii(x + cw, y + ch));
  336.                         nscale[i] = j;
  337.                         ax[i] = ay[i] = 0;
  338.                         orient[i] = now;
  339.                         int t = markBad(i);
  340.                         //if (t == -2) continue;
  341.                         if (t == -1) {
  342.                             ++cnt;
  343.                             continue;
  344.                         }
  345.                         int ns = beg;
  346.                         if (t != -2) ns -= mem[t];
  347.                         if (ns + 2 * cw + 2 * ch <= ans) continue;
  348.                         st[ssize++] = i;
  349.  
  350.                         if (t != -2) used[t] = 0;
  351.                         ns += getS(i);
  352.                         //if (ns < 0) cerr << "HER" << endl;
  353.                         //if (ns >= 10000000) cerr << "HER" << endl;
  354.                         if (t != -2) used[t] = 1;
  355.                         --ssize;
  356.                         if (ns > ans) {
  357.                             ans = ns;
  358.                             nt = t;
  359.                             nadd = i;
  360.                             wt = mp(pii(x, y), pii(j, now));
  361.                             /*if (t != -2) used[t] = 0;
  362.                             used[i] = 1;
  363.                             cerr << (double)ns / 10 << endl;
  364.                             ans = ns;
  365.                             rept(l, n) if (!used[l]) cord[l] = pii(-1, -1);
  366.                             refresh();*/
  367.                             //return;
  368.                         }
  369.                     }
  370.                     if (cnt == 2) break;
  371.                 }
  372.             }
  373.         }
  374.         if (stop) break;
  375.     }
  376.  
  377.     if (nadd != -1) {
  378.         if (nt >= 0) used[nt] = 0;
  379.         used[nadd] = 1;
  380.         cord[nadd] = wt.x;
  381.         nscale[nadd] = wt.y.x;
  382.         orient[nadd] = wt.y.y;
  383.         ax[nadd] = ay[nadd] = 0;
  384.         rept(l, n) if (!used[l]) cord[l] = pii(-1, -1);
  385.         refresh();
  386.     }
  387.  
  388.     if (ans == beg) return 0; else
  389.         return 1;
  390. }
  391.  
  392. bool nudge3() {
  393.     memcpy(orient, borient, sizeof(borient));
  394.     memcpy(cord, best, sizeof(best));
  395.     memcpy(ax, bax, sizeof(bax));
  396.     memcpy(ay, bay, sizeof(bay));
  397.     memcpy(nscale, bnscale, sizeof(bnscale));
  398.     opt = bopt;
  399.     ssize = 0;
  400.     VI xs, ys;
  401.     rept(i, n) {
  402.         if (best[i].x == -1) used[i] = 0; else
  403.             used[i] = 1;
  404.         rcord[i] = getCoord(i);
  405.         if (used[i]) {
  406.             st[ssize++] = i;
  407.             xs.pb(rcord[i].x.x);
  408.             xs.pb(rcord[i].y.x);
  409.             //xs.pb(rcord[i].x.x + ax[i]);
  410.             //xs.pb(rcord[i].y.x + ax[i]);
  411.  
  412.             ys.pb(rcord[i].x.y);
  413.             ys.pb(rcord[i].y.y);
  414.             //ys.pb(rcord[i].x.y + ay[i]);
  415.             //ys.pb(rcord[i].y.y + ay[i]);
  416.         }
  417.     }
  418.     rept(i, n) {
  419.         if (used[i]) mem[i] = getS(i);
  420.     }
  421.  
  422.     SORT(xs); xs.resize(unique(all(xs)) - xs.begin());
  423.     SORT(ys); ys.resize(unique(all(ys)) - ys.begin());
  424.  
  425.     random_shuffle(all(xs));
  426.     const int lf = 20;
  427.     if (L(xs) > lf) xs.resize(lf);
  428.     random_shuffle(all(ys));
  429.     if (L(ys) > lf) ys.resize(lf);
  430.  
  431.     int nt = -1, nadd = -1;
  432.     pair<pii, pii> wt;
  433.     int beg = ans;
  434.     bool stop = 0;
  435.     int o = 0;
  436.     rept(ii, L(xs)) {
  437.         int x = xs[ii];
  438.         rept(jj, L(ys)) {
  439.             int y = ys[jj];
  440.             if (stop || getTime() - startTime > 4.85) {
  441.                 stop = 1;
  442.                 break;
  443.             }
  444.             /*bool ok = 0;
  445.             rept(i, n) {
  446.             if (rcord[i].y.x == x && y >= rcord[i].x.y && y <= rcord[i].y.y) {
  447.             ok = 1;
  448.             break;
  449.             }
  450.             /*if (rcord[i].x == pii(x, y) || rcord[i].y == pii(x, y) || pii(rcord[i].x.x, rcord[i].y.y) == pii(x, y) || pii(rcord[i].y.x, rcord[i].x.y) == pii(x,y)) {
  451.             ok = 1;
  452.             break;
  453.             }
  454.             }
  455.             if (!ok) continue;*/
  456.  
  457.             rept(i, n) {
  458.                 if ((i & 7) == 0) {
  459.                     if (getTime() - startTime > 4.85) {
  460.                         stop = 1;
  461.                         break;
  462.                     }
  463.                 }
  464.                 bool u = used[i];
  465.                 //if (!u) continue;
  466.                 int s = ans, old_mem = mem[i];
  467.                 if (u) s -= mem[i];
  468.                 used[i] = 0;
  469.                 //if (used[i]) continue;
  470.                 rept(j, len[i]) {
  471.                     int cw = scaled[i][j].x, ch = scaled[i][j].y;
  472.                     if (s + 2 * cw + 2 * ch <= ans) continue;
  473.                     int now = 1, cnt = 0;
  474.                     rept(z, 2) {
  475.                         if (z == 1) {
  476.                             swap(cw, ch);
  477.                             now *= -1;
  478.                         }
  479.                         if (x + cw > w || y + ch > h) {
  480.                             ++cnt;
  481.                             continue;
  482.                         }
  483.  
  484.                         cord[i] = pii(x, y);
  485.                         rcord[i] = mp(pii(x, y), pii(x + cw, y + ch));
  486.                         nscale[i] = j;
  487.                         ax[i] = ay[i] = 0;
  488.                         orient[i] = now;
  489.                         int t = markBad(i);
  490.                         //if (t == -2) continue;
  491.                         if (t == -1) {
  492.                             ++cnt;
  493.                             continue;
  494.                         }
  495.                         int ns = s;
  496.                         if (t != -2) ns -= mem[t];
  497.                         if (ns + 2 * cw + 2 * ch <= ans) continue;
  498.                         st[ssize++] = i;
  499.  
  500.                         if (t != -2) used[t] = 0;
  501.                         ns += getS(i);
  502.                         //if (ns < 0) cerr << "HER" << endl;
  503.                         //if (ns >= 10000000) cerr << "HER" << endl;
  504.                         if (t != -2) used[t] = 1;
  505.                         --ssize;
  506.                         if (ns > ans) {
  507.                             ans = ns;
  508.                             if (t != -2) used[t] = 0;
  509.                             used[i] = 1;
  510.                             u = 0;
  511.                             ssize = 0;
  512.                             rept(l, n) if (used[l]) st[ssize++] = l;
  513.                             rept(l, n) if (used[l]) {
  514.                                 mem[l] = getS(l);
  515.                             }
  516.                             old_mem = mem[i];
  517.                             rcord[i] = getCoord(i);
  518.                             s = ans;
  519.                             //cerr << (double)ns / 10 << endl;
  520.                             ans = ns;
  521.                             rept(l, n) if (!used[l]) cord[l] = pii(-1, -1);
  522.                             refresh();
  523.                             //return;
  524.                         }
  525.                     }
  526.                     if (cnt == 2) break;
  527.                 }
  528.                 if (u) used[i] = 1;
  529.                 cord[i] = best[i];
  530.                 ax[i] = bax[i];
  531.                 ay[i] = bay[i];
  532.                 orient[i] = borient[i];
  533.                 nscale[i] = bnscale[i];
  534.                 rcord[i] = getCoord(i);
  535.                 mem[i] = old_mem;
  536.             }
  537.         }
  538.         if (stop) break;
  539.     }
  540.  
  541.     /*if (nadd != -1) {
  542.     if (nt >= 0) used[nt] = 0;
  543.     used[nadd] = 1;
  544.     cord[nadd] = wt.x;
  545.     nscale[nadd] = wt.y.x;
  546.     orient[nadd] = wt.y.y;
  547.     ax[nadd] = ay[nadd] = 0;
  548.     rept(l, n) if (!used[l]) cord[l] = pii(-1, -1);
  549.     refresh();
  550.     }*/
  551.  
  552.     if (ans == beg) return 0; else
  553.         return 1;
  554. }
  555.  
  556. inline void out() {
  557.     int fr = 0;
  558.     rept(i, n) if (best[i].x == -1) ++fr;
  559.     cerr << getTime() - startTime << " " << fr << " " << n << " " << (double)n * bopt / (w * h) << " " << T << endl;
  560.     rept(i, n) {
  561.         if (best[i].x == -1) {
  562.             printf("-1 -1 -1 -1\n");
  563.             continue;
  564.         }
  565.         int x1, y1, x2, y2;
  566.         x1 = best[i].x; y1 = best[i].y;
  567.         if (bax[i]) ++x1;
  568.         if (bay[i]) ++y1;
  569.         pii t = scaled[i][bnscale[i]];
  570.         if (borient[i] == -1) swap(t.x, t.y);
  571.         x2 = x1 + t.x; y2 = y1 + t.y;
  572.  
  573.         if (SW) {
  574.             swap(x1, y1);
  575.             swap(x2, y2);
  576.         }
  577.         printf("%s", toDouble(x1));
  578.         printf(" %s", toDouble(y1));
  579.         printf(" %s", toDouble(x2));
  580.         printf(" %s\n", toDouble(y2));
  581.     }
  582.     exit(0);
  583. }
  584. inline pair<pii, pii> getCoord(int v) {
  585.     int x1, y1, x2, y2;
  586.     x1 = cord[v].x, y1 = cord[v].y;
  587.     if (ax[v]) ++x1;
  588.     if (ay[v]) ++y1;
  589.     pii t = scaled[v][nscale[v]];
  590.     if (orient[v] == -1) swap(t.x, t.y);
  591.     x2 = x1 + t.x; y2 = y1 + t.y;
  592.     return mp(pii(x1, y1), pii(x2, y2));
  593. }
  594. inline void sumXY(int x1, int y1, int x2, int y2, int &sx, int &sy) {
  595.     //++CC;
  596.     //CC += ssize;
  597.     //if (ssize) CC += log((double)ssize) / log(2.0) * 3;
  598.     sx = sy = 0;
  599.     //rept(i, n) {
  600.     rept(i, ssize) {
  601.         int w = st[i];
  602.         pair<pii, pii> t = getCoord(w);
  603.         // sumY
  604.         if (t.y.x == x1) {
  605.             int l = max(y1, t.x.y);
  606.             int r = min(y2, t.y.y);
  607.             if (l < r) {
  608.                 if (orient[w] == 1) sy += r - l; else
  609.                     sy -= r - l;
  610.             }
  611.         }
  612.         // sumX
  613.         if (t.y.y == y1) {
  614.             int l = max(x1, t.x.x);
  615.             int r = min(x2, t.y.x);
  616.             if (l < r) {
  617.                 if (orient[w] == 1) sx += r - l; else
  618.                     sx -= r - l;
  619.             }
  620.         }
  621.     }
  622. }
  623. bool DEP;
  624. inline bool cmp(const pair<pii, pii> &a, const pair<pii, pii> &b) {
  625.     if (abs(a.x.x - b.x.x) > 0) return a.x.x > b.x.x;
  626.     pii t1 = scaled[a.x.y][a.y.x], t2 = scaled[b.x.y][b.y.x];
  627.     int sa = t1.x * t1.y;
  628.     int sb = t2.x * t2.y;
  629.     if (sa != sb) return abs(sa - opt) < abs(sb - opt);
  630.     //if (DEP) return a.y.x * len[b.x.y] < b.y.x * len[a.x.y];
  631.     //if (DEP) return abs((double)a.y.x / len[a.x.y] - 0.5) < abs((double)b.y.x / len[b.x.y] - 0.5);
  632.     //if (DEP) return (ll)sa * nomsq[a.x.y] < (ll)sb * nomsq[b.x.y];
  633.     if (a.y.y >> 2) swap(t1.x, t1.y);
  634.     if (b.y.y >> 2) swap(t2.x, t2.y);
  635.     //return t1.x * t2.y > t2.x * t1.y;
  636.     return t1.x > t2.x;
  637. }
  638. inline bool cmp2(const pair<pii, pii> &a, const pair<pii, pii> &b) {
  639.     //++CC;
  640.     if (abs(a.x.x - b.x.x) > 3) return a.x.x > b.x.x;
  641.     if (a.x.y == b.x.y && a.y.x == b.y.x) {
  642.         if ((a.y.y & 4) == (b.y.y & 4)) return 0;
  643.         if (scaled[a.x.y][a.y.x].x > scaled[a.x.y][a.y.x].y) return (a.y.y >> 2) ^ 1; else
  644.             return (a.y.y >> 2);
  645.     }
  646.     pii t1 = scaled[a.x.y][a.y.x], t2 = scaled[b.x.y][b.y.x];
  647.     int sa = t1.x * t1.y;
  648.     int sb = t2.x * t2.y;
  649.     if (a.y.y >> 2) swap(t1.x, t1.y);
  650.     if (b.y.y >> 2) swap(t2.x, t2.y);
  651.     //if (sa == sb) return t1.x * t2.y > t2.x * t1.y;
  652.     //if (DEP && sa == sb) return a.y.x * len[b.x.y] < b.y.x * len[a.x.y];
  653.     if (sa == sb) return t1.x * t2.y > t2.x * t1.y;
  654.     if (sa < opt || sb < opt) return sa > sb; else
  655.         return sa < sb;
  656. }
  657. inline int getS(int v) {
  658.     pair<pii, pii> t1 = getCoord(v);
  659.     int s = 0;
  660.     rept(i, ssize) {
  661.         int w = st[i];
  662.         if (!used[w] || w == v) continue;
  663.         pair<pii, pii> t2 = rcord[w];
  664.         int x1 = max(t1.x.x, t2.x.x);
  665.         int y1 = max(t1.x.y, t2.x.y);
  666.         int x2 = min(t1.y.x, t2.y.x);
  667.         int y2 = min(t1.y.y, t2.y.y);
  668.         if (x2 > x1 && y2 > y1) {
  669.             return -INF;
  670.         }
  671.         int add = 0;
  672.         if (x1 < x2 && y1 == y2) {
  673.             add = x2 - x1;
  674.             if (orient[w] == orient[v]) s -= add; else
  675.                 s += add;
  676.         }
  677.         if (y1 < y2 && x1 == x2) {
  678.             add = y2 - y1;
  679.             if (orient[w] == orient[v]) s -= add; else
  680.                 s += add;
  681.         }
  682.     }
  683.     return s;
  684. }
  685.  
  686.  
  687. double lastUpdate;
  688. bool EX;
  689.  
  690. const double limit = 2.0;
  691. int iter = 0;
  692. void rec(int s = 0, int depth = 0) {
  693.     ++T;
  694.     int bt = T;
  695.     if (s > updated_ans) updated_ans = s;
  696.     if (s > ans) {
  697.         iter = 0;
  698.         ans = s;
  699.         bopt = opt;
  700.         lastUpdate = getTime();
  701.         rept(i, n) {
  702.             if (used[i]) {
  703.                 best[i] = cord[i];
  704.                 bax[i] = ax[i];
  705.                 bay[i] = ay[i];
  706.                 borient[i] = orient[i];
  707.                 bnscale[i] = nscale[i];
  708.             } else
  709.                 best[i] = pii(-1, -1);
  710.         }
  711.     }
  712.  
  713.     double currentTime = getTime();
  714.     if (currentTime - startTime > 4.85) {
  715.         out();
  716.     }
  717.     if (currentTime - startTime > limit) {
  718.         return;
  719.     }
  720.     if (currentTime - lastUpdate > 0.05) {
  721.         //EX = 1;
  722.         return;
  723.     }
  724.     ++iter;
  725.     if (iter > 1000) return;
  726.     if (k == 2) return;
  727.  
  728.     pii t = pii(INF, INF);
  729.     int v = -1;
  730.     rep(i, k - 2) {
  731.         if (cur[i] < t) {
  732.             t = cur[i];
  733.             v = i;
  734.         }
  735.     }
  736.     if (v == -1) return;
  737.     if (cur[v].x >= w - 1 || cur[v].y >= h - 1) return;
  738.  
  739.     int can = s;
  740.     int rx = 0, ry = 0;
  741.     int sq = 0;
  742.     rept(i, k - 1) {
  743.         sq += cur[i].x * cur[i + 1].y - cur[i].y * cur[i + 1].x;
  744.         if (!cur[i].x && !cur[i + 1].x) continue;
  745.         if (!cur[i].y && !cur[i + 1].y) continue;
  746.         if (cur[i].y == h && cur[i + 1].y == h) continue;
  747.     }
  748.     sq += 0 * cur[0].y - h * cur[0].x;
  749.     if (sq < 0) sq = -sq;
  750.  
  751.     int per = 0, sum = 0;
  752.     rept(i, n) {
  753.         if (used[i]) continue;
  754.         FORD(j, len[i] - 1, 0) {
  755.             if (min(scaled[i][j].x, scaled[i][j].y) + cur[v].x > w) continue;
  756.             if (scaled[i][j].x * scaled[i][j].y * 2 + sq > 2 * w * h) continue;
  757.             per += scaled[i][j].x + scaled[i][j].y;
  758.             ry = max(ry, min(scaled[i][j].x, scaled[i][j].y));
  759.             break;
  760.         }
  761.     }
  762.     int add = 2 * per - ry;
  763.     can += add;
  764.     if (can <= ans) return;
  765.  
  766.  
  767.     int old_k = k, old_s = s;
  768.     pair<pii, int> old_cur[204];
  769.     memcpy(old_cur, cur, k * sizeof(pii));
  770.     // insert
  771.     int maxh = cur[v - 1].y - cur[v].y;
  772.     int maxw = w - cur[v].x;
  773.     int min_right = cur[v + 1].x - cur[v].x;
  774.     if (v - 2 >= 0) min_right = min(min_right, cur[v - 2].x - cur[v - 1].x);
  775.     int cnt = 0;
  776.     pair<pii, pii> cool = mp(pii(-1, -1), pii(-1, -1));
  777.     if (depth <= n / 8) DEP = 1; else
  778.         DEP = 0;
  779.     rept(i, n) {
  780.         if (used[i]) continue;
  781.         ++cnt;
  782.         FORD(j, len[i] - 1, 0) {
  783.             int cw = scaled[i][j].x, ch = scaled[i][j].y;
  784.             if (s + 2 * cw + 2 * ch < cool.x.x) continue;
  785.  
  786.             int now = 1;
  787.             rept(z, 2) {
  788.                 if (z == 1) {
  789.                     now = -now;
  790.                     swap(cw, ch);
  791.                 }
  792.                 if (cw > maxw || ch > maxh) continue;
  793.                 if (s + 2 * cw + ch < cool.x.x) continue;
  794.  
  795.                 int dx = 0, dy = 0;
  796.                 int sx = 0, sy = 0;
  797.                 sumXY(cur[v].x, cur[v].y, cur[v].x + cw, cur[v].y + ch, sx, sy);
  798.                 if (sy * now > 0) dx = 1;
  799.                 if (sx * now > 0) dy = 1;
  800.                 if (cur[v].x + cw + dx > w || cur[v].y + ch + dy > h) continue;
  801.  
  802.                 if (ch + dy < maxh) {
  803.                     cord[i] = cur[v];
  804.                     nscale[i] = j;
  805.                     orient[i] = now;
  806.                     ax[i] = dx; ay[i] = dy;
  807.  
  808.                     used[i] = 1;
  809.                     int ns = s + getS(i);
  810.                     used[i] = 0;
  811.                     if (ns > s || !s) {
  812.                         pair<pii, pii> cand = mp(pii(ns, i), pii(j, (z << 2) | (dx << 1) | dy));
  813.                         if (cool.x.x == -1 || cmp(cand, cool)) cool = cand;
  814.                     }
  815.                 } else {
  816.                     cord[i] = cur[v];
  817.                     nscale[i] = j;
  818.                     orient[i] = now;
  819.                     ax[i] = dx; ay[i] = dy;
  820.  
  821.                     used[i] = 1;
  822.                     int ns = s + getS(i);
  823.                     used[i] = 0;
  824.                     if (ns > s || !s) {
  825.                         pair<pii, pii> cand = mp(pii(ns, i), pii(j, (z << 2) | (dx << 1) | dy));
  826.                         if (cool.x.x == -1 || cmp(cand, cool)) cool = cand;
  827.                     }
  828.                 }
  829.                 s = old_s;
  830.             }
  831.         }
  832.     }
  833.     if (!cnt) return;
  834.     int ms = INF;
  835.     if (cool.x.x != -1) {
  836.         int i = cool.x.y;
  837.         int j = cool.y.x;
  838.         int z = cool.y.y >> 2;
  839.         int cw = scaled[i][j].x, ch = scaled[i][j].y;
  840.         int now = 1;
  841.         if (z == 1) {
  842.             now = -now;
  843.             swap(cw, ch);
  844.         }
  845.  
  846.         int dx = 0, dy = 0;
  847.         dx = (cool.y.y >> 1) & 1;
  848.         dy = (cool.y.y & 1);
  849.  
  850.         if (ch + dy < maxh) {
  851.             cord[i] = cur[v];
  852.             nscale[i] = j;
  853.             orient[i] = now;
  854.             ax[i] = dx; ay[i] = dy;
  855.             used[i] = 1;
  856.             s += getS(i);
  857.             used[i] = 0;
  858.             rcord[i] = getCoord(i);
  859.  
  860.             int ovp1 = cur[v + 1].x;
  861.             cur[v] = pii(cur[v].x, cur[v].y + dy + ch);
  862.             insert(k, v + 1, pii(cur[v].x + dx + cw, cur[v].y));
  863.             insert(k, v + 2, pii(cur[v + 1].x, cur[v + 1].y - dy - ch));
  864.             if (cur[v + 1].x > ovp1 && dy) {
  865.                 ++cur[v + 2].y; ++cur[v + 3].y;
  866.             }
  867.             normalize(k);
  868.         } else {
  869.             cord[i] = cur[v];
  870.             nscale[i] = j;
  871.             orient[i] = now;
  872.             ax[i] = dx; ay[i] = dy;
  873.             used[i] = 1;
  874.             s += getS(i);
  875.             used[i] = 0;
  876.             rcord[i] = getCoord(i);
  877.  
  878.             int ovp1 = cur[v + 1].y;
  879.             cur[v - 1] = pii(cur[v].x + dx + cw, cur[v].y + dy + ch);
  880.             cur[v] = pii(cur[v].x + dx + cw, cur[v].y);
  881.             if (dy && cur[v].x > ovp1) {
  882.                 ++cur[v].y; ++cur[v + 1].y;
  883.             }
  884.             normalize(k);
  885.         }
  886.         used[i] = 1;
  887.         st[ssize++] = i;
  888.         ms = min(ms, (scaled[i][j].x + dx) * (scaled[i][j].y + dy));
  889.         rec(s, depth + 1);
  890.         --ssize;
  891.         k = old_k;
  892.         memcpy(cur, old_cur, k * sizeof(pii));
  893.         s = old_s;
  894.         used[i] = 0;
  895.     }
  896.  
  897.     // not found
  898.     int shift = cur[v + 1].x - cur[v].x;
  899.     if (v >= 2) shift = min(shift, cur[v - 2].x - cur[v - 1].x);
  900.     if (shift * (cur[v - 1].y - cur[v].y) < ms) {
  901.         cur[v].x += shift; cur[v - 1].x += shift;
  902.         normalize(k);
  903.         rec(s, depth + 1);
  904.     }
  905. }
  906. void rec2(int s = 0, int depth = 0) {
  907.     ++T;
  908.     int bt = T;
  909.     if (s > ans) {
  910.         iter = 0;
  911.         ans = s;
  912.         bopt = opt;
  913.         lastUpdate = getTime();
  914.         rept(i, n) {
  915.             if (used[i]) {
  916.                 best[i] = cord[i];
  917.                 bax[i] = ax[i];
  918.                 bay[i] = ay[i];
  919.                 borient[i] = orient[i];
  920.                 bnscale[i] = nscale[i];
  921.             } else
  922.                 best[i] = pii(-1, -1);
  923.         }
  924.     }
  925.  
  926.     double currentTime = getTime();
  927.     if (currentTime - startTime > 4.85) {
  928.         out();
  929.     }
  930.     if (currentTime - startTime > TIME_LIMIT) {
  931.         return;
  932.         //out();
  933.     }
  934.     if (currentTime - lastUpdate > 0.05) {
  935.         EX = 1;
  936.         return;
  937.     }
  938.     ++iter;
  939.     if (iter > 1000) return;
  940.     if (k == 2) return;
  941.  
  942.     pii t = pii(INF, INF);
  943.     int v = -1;
  944.     rep(i, k - 2) {
  945.         if (cur[i] < t) {
  946.             t = cur[i];
  947.             v = i;
  948.         }
  949.     }
  950.     if (v == -1) return;
  951.     if (cur[v].x >= w - 1 || cur[v].y >= h - 1) return;
  952.  
  953.     int can = s;
  954.     int ry = 0;
  955.     int sq = 0;
  956.     rept(i, k - 1) {
  957.         sq += cur[i].x * cur[i + 1].y - cur[i].y * cur[i + 1].x;
  958.         if (!cur[i].x && !cur[i + 1].x) continue;
  959.         if (!cur[i].y && !cur[i + 1].y) continue;
  960.         if (cur[i].y == h && cur[i + 1].y == h) continue;
  961.     }
  962.     sq += 0 * cur[0].y - h * cur[0].x;
  963.     if (sq < 0) sq = -sq;
  964.  
  965.     int per = 0, sum = 0;
  966.     rept(i, n) {
  967.         if (used[i]) continue;
  968.         FORD(j, len[i] - 1, 0) {
  969.             if (min(scaled[i][j].x, scaled[i][j].y) + cur[v].x > w) continue;
  970.             if (scaled[i][j].x * scaled[i][j].y * 2 + sq > 2 * w * h) continue;
  971.             per += scaled[i][j].x + scaled[i][j].y;
  972.             ry = max(ry, min(scaled[i][j].x, scaled[i][j].y));
  973.             break;
  974.         }
  975.     }
  976.     int add = 2 * per - ry;
  977.     can += add;
  978.     if (can <= ans) return;
  979.  
  980.  
  981.     int old_k = k, old_s = s;
  982.     pair<pii, int> old_cur[204];
  983.     memcpy(old_cur, cur, k * sizeof(pii));
  984.     // insert
  985.     int maxh = cur[v - 1].y - cur[v].y;
  986.     int maxw = w - cur[v].x;
  987.     int min_right = cur[v + 1].x - cur[v].x;
  988.     if (v - 2 >= 0) min_right = min(min_right, cur[v - 2].x - cur[v - 1].x);
  989.     int cnt = 0;
  990.     vector<pair<pii, pii> > q;
  991.     rept(i, n) {
  992.         if (used[i]) continue;
  993.         ++cnt;
  994.         FORD(j, len[i] - 1, 0) {
  995.             int cw = scaled[i][j].x, ch = scaled[i][j].y;
  996.  
  997.             int now = 1;
  998.             rept(z, 2) {
  999.                 if (z == 1) {
  1000.                     now = -now;
  1001.                     swap(cw, ch);
  1002.                 }
  1003.                 if (cw > maxw || ch > maxh) continue;
  1004.  
  1005.                 int dx = 0, dy = 0;
  1006.                 int sx = 0, sy = 0;
  1007.                 sumXY(cur[v].x, cur[v].y, cur[v].x + cw, cur[v].y + ch, sx, sy);
  1008.                 if (sy * now > 0) dx = 1;
  1009.                 if (sx * now > 0) dy = 1;
  1010.                 if (cur[v].x + cw + dx > w || cur[v].y + ch + dy > h) continue;
  1011.  
  1012.                 if (ch + dy < maxh) {
  1013.                     cord[i] = cur[v];
  1014.                     nscale[i] = j;
  1015.                     orient[i] = now;
  1016.                     ax[i] = dx; ay[i] = dy;
  1017.  
  1018.                     used[i] = 1;
  1019.                     int ns = s + getS(i);
  1020.                     used[i] = 0;
  1021.                     if (ns > s || !s) q.pb(mp(pii(ns, i), pii(j, (z << 2) | (dx << 1) | dy)));
  1022.                 } else {
  1023.                     cord[i] = cur[v];
  1024.                     nscale[i] = j;
  1025.                     orient[i] = now;
  1026.                     ax[i] = dx; ay[i] = dy;
  1027.  
  1028.                     used[i] = 1;
  1029.                     int ns = s + getS(i);
  1030.                     used[i] = 0;
  1031.                     if (ns > s || !s) q.pb(mp(pii(ns, i), pii(j, (z << 2) | (dx << 1) | dy)));
  1032.                 }
  1033.                 s = old_s;
  1034.             }
  1035.         }
  1036.     }
  1037.     if (!cnt) return;
  1038.     if (!RN) {
  1039.         if (depth <= n / 2) DEP = 1; else
  1040.             DEP = 0;
  1041.         if (L(q) >= 2) partial_sort(q.begin(), q.begin() + 2, q.end(), cmp2);
  1042.     } else {
  1043.         sort(all(q)); reverse(all(q));
  1044.         int a = 0;
  1045.         while (a < L(q)) {
  1046.             int b = a;
  1047.             while (b < L(q) && q[a].x.x == q[b].x.x) ++b;
  1048.             random_shuffle(q.begin() + a, q.begin() + b);
  1049.             a = b;
  1050.         }
  1051.     }
  1052.  
  1053.     int ms = INF;
  1054.     rept(ii, L(q)) {
  1055.         if (ii == 1) break;
  1056.         int i = q[ii].x.y;
  1057.         int j = q[ii].y.x;
  1058.         int z = q[ii].y.y >> 2;
  1059.         if (used[i]) continue;
  1060.         int cw = scaled[i][j].x, ch = scaled[i][j].y;
  1061.         int now = 1;
  1062.         if (z == 1) {
  1063.             now = -now;
  1064.             swap(cw, ch);
  1065.         }
  1066.  
  1067.         if (cw > maxw || ch > maxh) continue;
  1068.  
  1069.         int dx = 0, dy = 0;
  1070.         dx = (q[ii].y.y >> 1) & 1;
  1071.         dy = (q[ii].y.y & 1);
  1072.         if (cur[v].x + cw + dx > w || cur[v].y + ch + dy > h) continue;
  1073.  
  1074.         if (ch + dy < maxh) {
  1075.             cord[i] = cur[v];
  1076.             nscale[i] = j;
  1077.             orient[i] = now;
  1078.             ax[i] = dx; ay[i] = dy;
  1079.             used[i] = 1;
  1080.             s += getS(i);
  1081.             used[i] = 0;
  1082.             rcord[i] = getCoord(i);
  1083.  
  1084.             int ovp1 = cur[v + 1].x;
  1085.             cur[v] = pii(cur[v].x, cur[v].y + dy + ch);
  1086.             insert(k, v + 1, pii(cur[v].x + dx + cw, cur[v].y));
  1087.             insert(k, v + 2, pii(cur[v + 1].x, cur[v + 1].y - dy - ch));
  1088.             if (cur[v + 1].x > ovp1 && dy) {
  1089.                 ++cur[v + 2].y; ++cur[v + 3].y;
  1090.             }
  1091.             normalize(k);
  1092.         } else {
  1093.             cord[i] = cur[v];
  1094.             nscale[i] = j;
  1095.             orient[i] = now;
  1096.             ax[i] = dx; ay[i] = dy;
  1097.             used[i] = 1;
  1098.             s += getS(i);
  1099.             used[i] = 0;
  1100.             rcord[i] = getCoord(i);
  1101.  
  1102.             int ovp1 = cur[v + 1].y;
  1103.             cur[v - 1] = pii(cur[v].x + dx + cw, cur[v].y + dy + ch);
  1104.             cur[v] = pii(cur[v].x + dx + cw, cur[v].y);
  1105.             if (dy && cur[v].x > ovp1) {
  1106.                 ++cur[v].y; ++cur[v + 1].y;
  1107.             }
  1108.             normalize(k);
  1109.         }
  1110.         used[i] = 1;
  1111.         st[ssize++] = i;
  1112.         ms = min(ms, scaled[i][j].x * scaled[i][j].y);
  1113.         rec2(s, depth + 1);
  1114.         --ssize;
  1115.         k = old_k;
  1116.         memcpy(cur, old_cur, k * sizeof(pii));
  1117.         s = old_s;
  1118.         used[i] = 0;
  1119.     }
  1120.  
  1121.     // not found
  1122.     int shift = cur[v + 1].x - cur[v].x;
  1123.     if (v >= 2) shift = min(shift, cur[v - 2].x - cur[v - 1].x);
  1124.     if (shift * (cur[v - 1].y - cur[v].y) < ms) {
  1125.         cur[v].x += shift; cur[v - 1].x += shift;
  1126.         normalize(k);
  1127.         rec2(s, depth + 1);
  1128.     }
  1129. }
  1130.  
  1131.  
  1132. int real_square[100001], rss;
  1133. set<int> bil;
  1134. map<int, int> replaced;
  1135. int main() {
  1136.     srand(25091992);
  1137.     startTime = getTime();
  1138.     //  freopen("input.txt","r",stdin);
  1139.     //  freopen("output.txt","w",stdout);
  1140.  
  1141.     scanf("%d%d%d", &w, &h, &n); w *= 10; h *= 10;
  1142.     if (w > h) {
  1143.         SW = 1;
  1144.         swap(w, h);
  1145.     }
  1146.     rept(i, n) {
  1147.         scanf("%d%d", &a, &b);
  1148.         if (SW) swap(a, b);
  1149.         nomsq[i] = a * b;
  1150.         FOR(j, a, w) {
  1151.             if (j > 20 * a) break;
  1152.             if (b * j % a == 0) {
  1153.                 scaled[i][len[i]++] = pii(j, b * j / a);
  1154.             }
  1155.         }
  1156.     }
  1157.  
  1158.     rept(i, n) {
  1159.         rept(j, len[i]) {
  1160.             real_square[rss++] = scaled[i][j].x * scaled[i][j].y;
  1161.         }
  1162.     }
  1163.     sort(real_square, real_square + rss);
  1164.     rss = unique(real_square, real_square + rss) - real_square;
  1165.  
  1166.     orient[101] = 2;
  1167.  
  1168.  
  1169.     lastUpdate = getTime();
  1170.  
  1171.     opt = w * h / n;
  1172.  
  1173.     int p1, p2, p3, s1, s2, s3;
  1174.     rept(hod, 3) {
  1175.         if (hod == 0 || hod == 1) {
  1176.             bil.clear();
  1177.             p1 = lower_bound(real_square, real_square + rss, w * h / (n + 1)) - real_square, s1 = 1;
  1178.             p2 = lower_bound(real_square, real_square + rss, w * h / n) - real_square, s2 = 1;
  1179.             p3 = lower_bound(real_square, real_square + rss, w * h / n * 4 / 3) - real_square, s3 = 1;
  1180.         }
  1181.         rept(i, 100000) {
  1182.             k = 0;
  1183.             cur[k++] = pii(0, h);
  1184.             cur[k++] = pii(0, 0);
  1185.             cur[k++] = pii(w, 0);
  1186.             if (i % 3 == 0) {
  1187.                 opt = real_square[p1];
  1188.                 p1 -= s1;
  1189.                 p1 %= rss;
  1190.                 if (p1 < 0) p1 += rss;
  1191.                 if (opt < s1) {
  1192.                     continue;
  1193.                 }
  1194.             } else
  1195.                 if (i % 3 == 1) {
  1196.                     opt = real_square[p2];
  1197.                     p2 += s2;
  1198.                     p2 %= rss;
  1199.                     if (opt > w * h + s2) continue;
  1200.                 } else
  1201.                     if (i % 3 == 2) {
  1202.                         opt = real_square[p3];
  1203.                         p3 += s3;
  1204.                         p3 %= rss;
  1205.                         if (opt > w * h + s3) continue;
  1206.                     }
  1207.                     int t = lower_bound(real_square, real_square + rss, opt) - real_square;
  1208.                     if (bil.count(t)) {
  1209.                         continue;
  1210.                     }
  1211.                     bil.insert(t);
  1212.                     //if (hod == 1 && replaced.count(opt) && replaced[opt] < (double)ans * 0.5) continue;
  1213.                     C(used); ssize = 0;
  1214.                     lastStart = lastUpdate = getTime();
  1215.                     updated_ans = 0;
  1216.                     iter = 0;
  1217.                     if (hod == 0) rec(); else
  1218.                         if (hod == 1 || hod == 2) rec2();
  1219.  
  1220.                     if (hod == 0) replaced[opt] = updated_ans;
  1221.                     if (hod == 0 && getTime() - startTime > limit) break;
  1222.                     if (hod == 1 && getTime() - startTime > TIME_LIMIT) break;
  1223.         }
  1224.  
  1225.         if (hod == 1) {
  1226.             int cnt = 0;
  1227.             rept(i, 30000) {
  1228.                 int old = ans;
  1229.                 //if (!nudge()) ++cnt;
  1230.                 //if (getTime() - startTime > 4.85) break;
  1231.                 //if (!nudge2()) ++cnt;
  1232.                 if (!nudge3()) ++cnt;
  1233.                 //if (cnt == 2) break;
  1234.                 //if (ans != old) cerr << "WOW " << (double)ans / 10.0 << endl;
  1235.                 if (getTime() - startTime > 4.85) break;
  1236.                 //if (cnt == 4) break;
  1237.             }
  1238.             if (getTime() - startTime > 4.85) out();
  1239.         }
  1240.     }
  1241.     //wtf
  1242.     //cerr << "HERE" << endl;
  1243.     out();
  1244. }
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!