fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define vc vector
  5. #define F first
  6. #define S second
  7. #define yes cout << "YES" << "\n"
  8. #define no cout << "NO" << "\n"
  9. #define el "\n"
  10. #define pb push_back
  11. #define pf push_front
  12. #define all(x) (x).begin(),(x).end()
  13. #define rall(x) (x).rbegin(),(x).rend()
  14. #define fr(i,x,n) for(int i = x ; i< n ;i++)
  15. #define cin(v) for(auto& ele : v)cin>>ele
  16. #define print(v) for(auto& ele : v)cout << ele << ' '
  17. #define test(x,y) cout << x << ' ' << y << "\n"
  18. #define debug(x) cout << "x : " << x << el
  19. #define vc2Dint vector<vector<int>>
  20. #define vc2Dll vector<vector<long long>>
  21. #define cin2D(v) for(auto& row : (v))for(auto& col : row)cin>>col
  22. #define print2D(v) for(auto& row : v){for(auto& col: row)cout << col << ' ';cout << el;}
  23. #define flush cout << flush
  24.  
  25.  
  26. using namespace std;
  27.  
  28.  
  29. // math equation is (a*n^2)+(b*n)+c = 0 : (-b±√(b²-4ac))/(2a)  : (-b +/- sqrt(b^2 - 4*a*c))/2*a;
  30. //sum form 1 to n in o(1)
  31. //0 -> n  : (n*(n+1))/2;
  32. //0 -> n reversed if he gives you the sum and want the number ((-1+sqrt(1+(8*n)))/2) -> he give you 15 and want to get the number that sum is 15 it is 5.
  33. //0 -> n ODD : ((n+1)/2)*((n+1)/2);
  34. //0 -> n EVEN : (n/2)*((n/2)+1);
  35. //0 -> n that is divisible by x : ((n / x)) * (2 * x + (n / x - 1) * x) / 2;
  36. //0 -> n of fibonacci numbers is : fib(n+2)-1;
  37. //count numbers from 1 to n
  38. // n EVEN : n/2;
  39. // n ODD : (n+1)/2;
  40.  
  41. // arithmetic progression
  42. // an = a + (n-1) * d ;
  43. // a -> first term , n -> number of terms , d -> common difference
  44. // ex : 1,3,5,7,9,....
  45. // a4 = 1 + (4-1) * 2 = 7
  46.  
  47. // ceil(x/y) = (x+y-1)/y
  48.  
  49. // ASCII : A->Z ( 65 <= x && x <= 90) , a->z (97 <= x && x <= 122)
  50.  
  51.  
  52. bool getBit(ll x, ll idx) { return x & (1LL << idx); }
  53. int setBit1(int x, int idx) { return x | (1 << idx); }
  54. int setBit0(int x, int idx) { return x & ~(1 << idx); }
  55. int toggleBit(int x, int idx) { return x ^ (1 << idx); }
  56.  
  57.  
  58. int cntBit(int x)
  59. {
  60.     int cnt = 0;
  61.     while (x)
  62.     {
  63.         if (x % 2)cnt++;
  64.         x /= 2;
  65.     }
  66.     return cnt;
  67. }
  68.  
  69.  
  70. string fromDeci(ll n, ll base) {
  71.     if (n == 0) return "0";
  72.     string res = "";
  73.     while (n > 0) {
  74.         int rem = n % base;
  75.         if (rem < 10) res += (rem + '0');
  76.         else res += (rem - 10 + 'A');
  77.         n /= base;
  78.     }
  79.     reverse(res.begin(), res.end());
  80.     return res;
  81. }
  82.  
  83. ll toDeci(string n,ll base){
  84.     ll result = 0;
  85.     ll base_power = 1;
  86.  
  87.     for(int i = n.size() - 1; i >= 0; i--) {
  88.         int digit_value;
  89.         if(n[i] >= '0' && n[i] <= '9') {
  90.             digit_value = n[i] - '0';
  91.         } else {
  92.             digit_value = n[i] - 'A' + 10;
  93.         }
  94.         result += digit_value * base_power;
  95.         base_power *= base;
  96.     }
  97.  
  98.     return result;
  99. }
  100.  
  101. // ================================== bitmask built in functions ==================================
  102. // __builtin_popcount(unsigned int)returns the number of set bits
  103. // __builtin_ffs(int) finds the index of the first (most right) set bit
  104. // __builtin_ctz(unsigned int) the count of trailing zeros(right zeros)
  105. // __builtin_clz(unsigned int) the count of leading zeros (left zeros)
  106.  
  107. // ================================== math theory functions ==================================
  108. //12351362143262364334723457224234543237632456 + 416324274732532425243725344352426234
  109. // sum very big numbers
  110. struct BigInteger {
  111.     string str;
  112.  
  113.     // Constructor to initialize
  114.     // BigInteger with a string
  115.     BigInteger(string s) { str = s; }
  116.  
  117.     // Overload + operator to add
  118.     // two BigInteger objects
  119.     BigInteger operator+(const BigInteger& b)
  120.     {
  121.         string a = str;
  122.         string c = b.str;
  123.         int alen = a.length(), clen = c.length();
  124.         int n = max(alen, clen);
  125.         if (alen > clen)
  126.             c.insert(0, alen - clen, '0');
  127.         else if (alen < clen)
  128.             a.insert(0, clen - alen, '0');
  129.         string res(n + 1, '0');
  130.         int carry = 0;
  131.         for (int i = n - 1; i >= 0; i--) {
  132.             int digit = (a[i] - '0') + (c[i] - '0') + carry;
  133.             carry = digit / 10;
  134.             res[i + 1] = digit % 10 + '0';
  135.         }
  136.         if (carry == 1) {
  137.             res[0] = '1';
  138.             return BigInteger(res);
  139.         }
  140.         else {
  141.             return BigInteger(res.substr(1));
  142.         }
  143.     }
  144.  
  145.     // Overload << operator to output
  146.     // BigInteger object
  147.     friend ostream& operator<<(ostream& out,
  148.                                const BigInteger& b)
  149.     {
  150.         out << b.str;
  151.         return out;
  152.     }
  153. };
  154.  
  155.  
  156. vc<ll> getDivisors(ll n)
  157. {
  158.     vc<ll> v;
  159.     ll i = 1;
  160.     for (; i * i < n; i++)
  161.     {
  162.         if (n % i == 0)
  163.         {
  164.             v.pb(i);
  165.             v.pb(n / i);
  166.         }
  167.     }
  168.     if (i * i == n)v.pb(i);
  169.     return v;
  170. }
  171.  
  172. vc<bool> sieve(ll n)
  173. {
  174.     vc<bool> is_prime(n + 1, true);
  175.     is_prime[0] = is_prime[1] = false;
  176.     for (int i = 2; i * i <= n; i++)
  177.     {
  178.         if (is_prime[i]) { for (int j = i * i; j <= n; j += i)is_prime[j] = false; }
  179.     }
  180.     return is_prime;
  181. }
  182.  
  183. vc<ll> SieveOfEratosthenes(ll n)
  184. {
  185.     vc<ll> primes;
  186.     vc<bool> is_prime = sieve(n);
  187.     for(ll i = 2; i < n + 1; i++)
  188.     {
  189.        if (is_prime[i])
  190.            primes.pb(i);
  191.     }
  192.     return primes;
  193. }
  194.  
  195. bool isPrime(ll number)
  196. {
  197.     if (number < 2) { return false; }
  198.     if (number == 2 || number == 3 || number == 5) { return true; }
  199.     if (number % 2 == 0 || number % 3 == 0 || number % 5 == 0) { return false; }
  200.     for (ll i = 5; i * i <= number; i += 6) { if (number % i == 0 || number % (i + 2) == 0) { return false; } }
  201.     return true;
  202. }
  203.  
  204. vc<ll> primeFactorization(ll n){
  205.     vc<ll> result;
  206.     while(n % 2 == 0)
  207.     {
  208.         result.pb(2);
  209.         n = n/2;
  210.     }
  211.  
  212.     for(ll i = 3; i*i <= n; i = i + 2)
  213.     {
  214.         while(n % i == 0)
  215.         {
  216.             result.pb(i);
  217.             n = n/i;
  218.         }
  219.     }
  220.  
  221.     if(n > 2)
  222.         result.pb(n);
  223.  
  224.     return result;
  225. }
  226.  
  227. ll absMod(ll x , ll mod){return ((x%mod)+mod) % mod;}
  228. ll add(ll a,ll b,ll m) { return ((a % m) + (b % m)) % m; }
  229. ll mul(ll a,ll b,ll m) { return ((a % m) * (b % m)) % m; }
  230. ll sub(ll a,ll b,ll m) { return ((a % m) - (b % m) + m) % m; }
  231. ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
  232. ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
  233.  
  234. ll factorial(ll n)
  235. {
  236.     if (n == 0)return 1;
  237.     ll i = n, fact = 1;
  238.     while (n / i != n)
  239.     {
  240.         fact = fact*i;
  241.         i--;
  242.     }
  243.     return fact;
  244. }
  245.  
  246. ll npr(ll n, ll r) { return factorial(n) / factorial(n - r); }
  247. ll ncr(ll n, ll r) { return npr(n, r) / factorial(r); }
  248.  
  249. // ================================== random functions ==================================
  250. void srour()
  251. {
  252.     ios_base::sync_with_stdio(false);
  253.     cin.tie(nullptr);
  254.     cout.tie(nullptr);
  255. }
  256.  
  257. ll power(ll x, ll y,ll mod)
  258. {
  259.     ll res = 1;
  260.     while (y > 0)
  261.     {
  262.         if (y % 2 == 1)res = mul(res,x,mod);
  263.         y = y >> 1;
  264.         x = mul(x,x,mod);
  265.     }
  266.     return res;
  267. }
  268. ll power(ll x, ll y){
  269.     ll res = 1;
  270.     while (y > 0)
  271.     {
  272.         if (y % 2 == 1)res *= x;
  273.         y = y >> 1;
  274.         x *= x;
  275.     }
  276.     return res;
  277. }
  278.  
  279. bool isDivisibleByPowerOf2(int n, int k) { return (n & (1 << k - 1)) == 0; }
  280. bool isPowerOfTwo(unsigned ll n) { return n && !(n & (n - 1)); }
  281.  
  282.  
  283.  
  284. /*
  285.  
  286.  
  287.       ██████  ██▀███   ▒█████   █    ██  ██▀███
  288.     ▒██    ▒ ▓██ ▒ ██▒▒██▒  ██▒ ██  ▓██▒▓██ ▒ ██▒
  289.     ░ ▓██▄   ▓██ ░▄█ ▒▒██░  ██▒▓██  ▒██░▓██ ░▄█ ▒
  290.       ▒   ██▒▒██▀▀█▄  ▒██   ██░▓▓█  ░██░▒██▀▀█▄
  291.     ▒██████▒▒░██▓ ▒██▒░ ████▓▒░▒▒█████▓ ░██▓ ▒██▒
  292.     ▒ ▒▓▒ ▒ ░░ ▒▓ ░▒▓░░ ▒░▒░▒░ ░▒▓▒ ▒ ▒ ░ ▒▓ ░▒▓░
  293.     ░ ░▒  ░ ░  ░▒ ░ ▒░  ░ ▒ ▒░ ░░▒░ ░ ░   ░▒ ░ ▒░
  294.     ░  ░  ░    ░░   ░ ░ ░ ░ ▒   ░░░ ░ ░   ░░   ░
  295.           ░     ░         ░ ░     ░        ░
  296.  
  297.  
  298.  
  299. ================================================== start of code ==================================================
  300.  
  301.  
  302.  
  303.  */
  304.  
  305.  
  306.  
  307.  
  308. /*
  309.     ------------>>> First thing  you should think <<<---------------
  310.  
  311.     ACE -> very easy problem.
  312.     implementation -> solve only without thinking of algorithm.
  313.     greedy -> try to find pattern in the problem.
  314.     math -> try to find a formula for the problem.
  315.  
  316.     ------------>>> Second thing  you should think <<<---------------
  317.  
  318.     STLs:-
  319.  
  320.     sequential containers
  321.         $ vector -> one direction dynamic array can v.(puch_back,pop_back,front,back,begin,end,erase)
  322.         $ deque ->  multi direction dynamic array can dq.(push_back,pop_back,push_front,pop_front,front,back,begin,end)
  323.         $ array -> array<type,sizeOfArray> used for fixed multidimensional array vc<array<int,5>>
  324.  
  325.     container adapters
  326.         $ stack -> LIFO(last in first out)
  327.         - used for problems that connect two element together like "(),{},[]" it can also be numbers.
  328.         $ queue -> FIFO(first in last out)
  329.         - used for problems that
  330.         $ priority_queue -> sort all elements increasing by default priority_queue<int,vc<int>,greater<int>> to reverse
  331.  
  332.     associative container
  333.         $ set -> unique and sorted data structure st.(insert,erase(val),find)
  334.         $ multiset -> sorted data structure like a priority queue but can access to any element.
  335.         $ map ->
  336.  
  337.     prefix sum:-
  338.             ...........IDK.
  339.  
  340.     Binary search:-
  341.  
  342.         $ lower_bound -> get the number or the number next to ex : *lower_bound(5) = 5 -> [2,3,5,7,8]
  343.         $ upper_bound -> get the next number ex: *upper_bound(5) = 7 -> [2,3,5,7,8]
  344.         $ binary search on ranges ->
  345.         $ binary search on answer ->
  346.  
  347.     Bitmask:-
  348.         $ greedy -> most of time bitmask problems solved by patterns.
  349.         $ ACE -> should know some formulas like : .....Forgot.
  350.  
  351.     number theory:-
  352.  
  353.         $ GCD ->
  354.         $ LCM ->
  355.         $ Implementation ->
  356.  
  357. --------------------------------------- tips && tricks ---------------------------------------
  358.  
  359. 1-erase(unique(all(v)),v.end()) -> remove repeated elements in the array sequentially [1,1,2,2,3,2,1] -> [1,2,3,2,1]
  360. 2-sort(all(v)) -> erase(unique(all(v)),v.end()) -> remove all repeated elements in the hole array [1,1,2,2,3,2,1] -> [1,2,3]
  361.  
  362.  
  363. */
  364.  
  365. ll mod = 1e9+7, oo = 0x3f3f3f3f;
  366. const double PI = acosl(-1.0l);
  367. const int dx[] = {0,0,1,-1/*,1,-1,1,-1*/};
  368. const int dy[] = {1,-1,0,0/*,1,-1,-1,1*/};
  369. const double EPS = 1e-7;//epsilon
  370. const int N = 2e5+5;
  371.  
  372. // interactive
  373. string ask(int md){
  374.     cout << md << el;
  375.     flush;
  376.     string x;cin>>x;
  377.     return x;
  378. }
  379.  
  380. /*
  381.  
  382.     data type range
  383.     data structure
  384.     algorithm
  385.  
  386.  
  387.  
  388. ======== test Cases ========
  389. Input:
  390. 10 5
  391. 2 3 0 0 0 2 3 1 1 0
  392. 7
  393. 1 2
  394. 1 3
  395. 1 7
  396. 1 10
  397. 2 7
  398. 2 6
  399. 3 8
  400.  
  401. Output:
  402.  
  403.  
  404. */
  405.  
  406.  
  407.  
  408.  
  409.  
  410. void solve(){
  411.     int op = 30;
  412.     int l = 0 ,r = 1e9;
  413.     while(op-- && l <= r){
  414.         int md = (l+r)>>1;
  415.         string res = ask(md);
  416.         if(res == "=")return void(cout << "! " << md << el);
  417.         else if(res == ">")l = md+1;
  418.         else r = md-1;
  419.     }
  420.  
  421. }
  422.  
  423.  
  424.  
  425.  
  426.  
  427. //-------------------- tips and tricks -------------------------
  428. // BEFORE coding are you sure you understood the statement correctly?
  429. // PLEASE do not forget to read the sample explanation carefully.
  430. // WATCH out for overflows & RTs in general.
  431. // TEST your idea or code on the corner cases.
  432. // ANALYZE each idea you have thoroughly.
  433. // IS not binary search on answer?
  434. // IF there is subtasks in the problem.
  435.  
  436.  
  437. int main(){
  438. //    freopen("mosalah.in", "r", stdin);
  439. //    freopen("Output.in", "w", stdout);
  440.  
  441.     srour();
  442.     int t = 1;
  443. //    cin>>t;
  444.     while (t--)
  445.         solve();
  446.     return 0;
  447. }
  448.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
500000000
249999999
124999999
62499999
31249999
15624999
7812499
3906249
1953124
976561
488280
244139
122069
61034
30516
15257
7628
3813
1906
952
475
237
118
58
28
13
6
2
0
https://ideone.com/LtoUXz
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

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!