fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <cctype>
  7. #include <stack>
  8. #include <queue>
  9. #include <vector>
  10. #include <map>
  11. #include <sstream>
  12. #include <cmath>
  13. #include <limits>
  14. #include <utility>
  15. #include <iomanip>
  16. #include <set>
  17. #include <numeric>
  18. #include <cassert>
  19. #include <ctime>
  20.  
  21. #define INF_MAX 2147483647
  22. #define INF_MIN -2147483647
  23. #define INF_LL 9223372036854775807LL
  24. #define INF 2000000000
  25. #define PI acos(-1.0)
  26. #define EPS 1e-8
  27. #define LL long long
  28. #define mod 1000000007
  29. #define pb push_back
  30. #define mp make_pair
  31. #define f first
  32. #define s second
  33. #define setzero(a) memset(a,0,sizeof(a))
  34. #define setdp(a) memset(a,-1,sizeof(a))
  35. #define bits(a) __builtin_popcount(a)
  36.  
  37. using namespace std;
  38.  
  39. set<pair<LL, LL> > s;
  40. bool test;
  41.  
  42. void solve(LL &xx, LL &yy, bool yes)
  43. {
  44.   set<pair<LL, LL> >::iterator it = s.lower_bound(mp(xx, xx));
  45.   set<pair<LL, LL> >::iterator it2 = s.lower_bound(mp(yy, yy));
  46.   if(it == s.end())
  47.     it--;
  48.   if(it2 == s.end())
  49.     it2--;
  50.   pair<LL, LL> L = *it, R = *it2;
  51.   if(yes)
  52.   {
  53.     if(R.s < xx)
  54.     {
  55.       test = false;
  56.       return;
  57.     }
  58.     if(L.f > yy && it == s.begin())
  59.     {
  60.       test = false;
  61.       return;
  62.     }
  63.     if(L.f > xx && it == s.begin())
  64.     {
  65.       if(R.f > yy)
  66.       {
  67.         it2--;
  68.         R = *it2;
  69.       }
  70.       L = mp(R.f, min(yy, R.s));
  71.       it = it2;
  72.       while(it2 != s.end())
  73.       {
  74.         it++;
  75.         s.erase(it2);
  76.         it2 = it;
  77.       }
  78.       s.insert(L);
  79.     }
  80.     else
  81.     {
  82.       if(R.f > yy)
  83.       {
  84.         it2--;
  85.         R = *it2;
  86.       }
  87.       if(L.f > xx)
  88.       {
  89.         it--;
  90.         L = *it;
  91.       }
  92.       if(L.s < xx)
  93.       {
  94.         if(it == it2)
  95.         {
  96.           test = false;
  97.           return;
  98.         }
  99.         it++;
  100.         L = *it;
  101.       }
  102.       if(it == it2)
  103.       {
  104.         L = mp(max(xx, L.f), min(yy, R.s));
  105.         s.clear();
  106.         s.insert(L);
  107.         return;
  108.       }
  109.       L = mp(max(xx, L.f), L.s);
  110.       R = mp(R.f, min(yy, R.s));
  111.       set<pair<LL, LL> >::iterator it3 = it, it4;
  112.       it4 = it3;
  113.       while(1)
  114.       {
  115.         if(it3 == it)
  116.         {
  117.           s.erase(it);
  118.           break;
  119.         }
  120.         it4++;
  121.         s.erase(it3);
  122.         it3 = it4;
  123.       }
  124.       it3 = it2;
  125.       it4 = it3;
  126.       while(it3 != s.end())
  127.       {
  128.         it4++;
  129.         s.erase(it3);
  130.         it3 = it4;
  131.       }
  132.       s.insert(L);
  133.       s.insert(R);
  134.     }
  135.   }
  136.   else
  137.   {
  138.     if(R.s < xx)
  139.       return;
  140.     if(L.f > yy && it == s.begin())
  141.       return;
  142.     if(L.f > xx && it == s.begin())
  143.     {
  144.       if(R.f > yy)
  145.       {
  146.         it2--;
  147.         R = *it2;
  148.       }
  149.       L = mp(yy + 1, R.s);
  150.       it = it2;
  151.       while(1)
  152.       {
  153.         if(it2 == s.begin())
  154.         {
  155.           s.erase(it2);
  156.           break;
  157.         }
  158.         it--;
  159.         s.erase(it2);
  160.         it2 = it;
  161.       }
  162.       if(L.f <= L.s)
  163.         s.insert(L);
  164.     }
  165.     else
  166.     {
  167.       if(R.f > yy)
  168.       {
  169.         it2--;
  170.         R = *it2;
  171.       }
  172.       if(L.f > xx)
  173.       {
  174.         it--;
  175.         L = *it;
  176.       }
  177.       if(L.s < xx)
  178.       {
  179.         if(it == it2) return;
  180.         it++;
  181.         L = *it;
  182.       }
  183.       bool can = true;
  184.       if(it == it2)
  185.       {
  186.         s.erase(it);
  187.         can = false;
  188.       }
  189.       L = mp(L.f, xx - 1);
  190.       R = mp(yy + 1, R.s);
  191.       set<pair<LL, LL> >::iterator it3 = it;
  192.       while(can)
  193.       {
  194.         if(it == it2)
  195.         {
  196.           s.erase(it);
  197.           break;
  198.         }
  199.         it3++;
  200.         s.erase(it);
  201.         it = it3;
  202.       }
  203.       if(L.f <= L.s)
  204.         s.insert(L);
  205.       if(R.f <= R.s)
  206.         s.insert(R);
  207.     }
  208.     test &= (s.size() != 0);
  209.   }
  210. }
  211.  
  212. int main()
  213. {
  214.   //ios_base::sync_with_stdio(0);
  215.   //freopen("lca.in", "r", stdin);
  216.   //freopen("lca.out", "w", stdout);
  217.   int n, q, lev;
  218.   LL x, y;
  219.   int yes;
  220.   scanf("%d %d", &n, &q);
  221.   s.insert(mp(1LL << (n - 1), (1LL << n) - 1));
  222.   test = true;
  223.   while(q-- && test)
  224.   {
  225.     scanf("%d %I64d %I64d %d", &lev, &x, &y, &yes);
  226.     for(int i=lev;i<n && test;i++)
  227.     {
  228.       x = x * 2;
  229.       y = y * 2 + 1;
  230.     }
  231.     solve(x, y, yes);
  232.   }
  233.   if(!test)
  234.     cout << "Game cheated!";
  235.   else
  236.   {
  237.     pair<LL, LL> res;
  238.     if(s.size() == 1)
  239.     {
  240.       res = *s.lower_bound(mp(0, 0));
  241.       if(res.f != res.s) test = false;
  242.     }
  243.     else test = false;
  244.     if(!test)
  245.       cout << "Data not sufficient!";
  246.     else cout << res.f;
  247.   }
  248.   return 0;
  249. }
Success #stdin #stdout 0s 3236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Game cheated!
https://ideone.com/s8HPBx
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!