Submission #679114

# Submission time Handle Problem Language Result Execution time Memory
679114 2023-01-07T13:28:23 Z Hacv16 Aliens (IOI07_aliens) C++17
Compilation error
0 ms 0 KB
#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define int long long

int n, x, y, m, numblock, numq;
 
bool check(int x){ return x > 0 && x <= n ;}

bool query(int x, int y){
    if(!check(x) || !check(y)) return false;
    assert(++numq <= 300);
    cout << "examine " << x << ' ' << y << '\n'; fflush(stdout);
    string ans; cin >> ans; return (ans == "true");
}

pair<int, int> findCenter(int x, int y, int m){
    int l = 0, r = 2 * n / m, curx = x, cury = y, jump = 0;
 
    //Diagonal jump
    while(l <= r){
        int mid = (l + r) >> 1;
        int nx = curx + m * mid, ny = cury + m * mid;
        if(query(nx, ny)) l = mid + 1, jump = mid;
        else r = mid - 1;
    }   
 
    curx += jump * m;
    cury += jump * m;
 
    l = 0, r = ((n + m - 1) / m), jump = 0;
 
    //Upwards jump
    while(l <= r){
        int mid = (l + r) >> 1;
        int ny = cury + m * (2 * mid);
        if(query(curx, ny)) l = mid + 1, jump = 2 * mid;
        else r = mid - 1;
    }
 
    cury += jump * m;
 
    //Left jump
    l = 0, r = ((n + m - 1)/ m), jump = 0;
 
    while(l <= r){
        int mid = (l + r) >> 1;
        int nx = curx - m * (2 * mid);
        if(query(nx, cury)) l = mid + 1, jump = 2 * mid;
        else r = mid - 1;
    }
 
    curx -= jump * m;
    
    //move to center of current block
    curx += (m - 1) / 2;
    cury -= (m - 1) / 2;
    
    //move to center block
    l = 0, r = ((n + m - 1) / m), jump = 0;
 
    while(l <= r){
        int mid = (l + r) >> 1;
        int nx = curx + m * (2 * mid);
        if(query(nx, cury)) l = mid + 1, jump = 2 * mid;
        else r = mid - 1;
    }
 
    numblock = jump + 1;
 
    curx += ((numblock - 1) / 2) * m;
    cury -= ((numblock - 1) / 2) * m;
    
    return {curx, cury};
}

pair<int, int> getPos(int x, int y, int dx, int dy){
    int pw = 0;

    for(int i = 0; i < 31; i++)
        if(!query(x + dx * (1 << i), y + dy * (1 << i))){ pw = i; break; }

    if(dx == 0 && dy == 1){
        int l = y, r = min(n, y + (1 << pw));

        while(l <= r){
            int mid = (l + r) >> 1;
            if(query(x, mid)) l = mid + 1;
            else r = mid - 1;
        }

        return {x, max(y, l - 1)};

    }else if(dx == 0 && dy == -1){
        int l = max(1, y - (1 << pw)), r = y;

        while(l <= r){
            int mid = (l + r) >> 1;
            if(query(x, mid)) r = mid - 1;
            else l = mid + 1;
        }

        return {x, min(y, r + 1)};

    }else{
        int l = max(1, x - (1 << pw)), r = x;

        while(l <= r){
            int mid = (l + r) >> 1;
            if(query(mid, y)) r = mid - 1;
            else l = mid + 1;
        }
        return {min(x, r + 1), y};
    }

    return {x, y};
}
 
int32_t main(){
    cin >> n >> x >> y;

    pair<int, int> top = getPos(x, y, 0, 1);
    pair<int, int> bot = getPos(x, y, 0, -1);
    pair<int, int> lef = getPos(x, y, -1, 0);

    int m = top.second - bot.second + 1, cury = top.second, curx = lef.first;

    pair<int, int> resp = findCenter(curx, cury, m);

    cout << "solution " << resp.first << ' ' << resp.second << '\n';

    exit(0);
}

Compilation message

aliens.cpp: In function 'std::pair<long long int, long long int> getPos(long long int, long long int, long long int, long long int)':
aliens.cpp:98:37: error: no matching function for call to 'max(int, long long int)'
   98 |         int l = max(1, y - (1 << pw)), r = y;
      |                                     ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
aliens.cpp:98:37: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   98 |         int l = max(1, y - (1 << pw)), r = y;
      |                                     ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
aliens.cpp:98:37: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   98 |         int l = max(1, y - (1 << pw)), r = y;
      |                                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
aliens.cpp:98:37: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   98 |         int l = max(1, y - (1 << pw)), r = y;
      |                                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
aliens.cpp:98:37: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   98 |         int l = max(1, y - (1 << pw)), r = y;
      |                                     ^
aliens.cpp:100:20: error: 'r' was not declared in this scope
  100 |         while(l <= r){
      |                    ^
aliens.cpp:106:27: error: 'r' was not declared in this scope
  106 |         return {x, min(y, r + 1)};
      |                           ^
aliens.cpp:106:33: error: could not convert '{x, <expression error>}' from '<brace-enclosed initializer list>' to 'std::pair<long long int, long long int>'
  106 |         return {x, min(y, r + 1)};
      |                                 ^
      |                                 |
      |                                 <brace-enclosed initializer list>
aliens.cpp:109:37: error: no matching function for call to 'max(int, long long int)'
  109 |         int l = max(1, x - (1 << pw)), r = x;
      |                                     ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
aliens.cpp:109:37: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  109 |         int l = max(1, x - (1 << pw)), r = x;
      |                                     ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
aliens.cpp:109:37: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  109 |         int l = max(1, x - (1 << pw)), r = x;
      |                                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
aliens.cpp:109:37: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  109 |         int l = max(1, x - (1 << pw)), r = x;
      |                                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
aliens.cpp:109:37: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  109 |         int l = max(1, x - (1 << pw)), r = x;
      |                                     ^
aliens.cpp:111:20: error: 'r' was not declared in this scope
  111 |         while(l <= r){
      |                    ^
aliens.cpp:116:24: error: 'r' was not declared in this scope
  116 |         return {min(x, r + 1), y};
      |                        ^
aliens.cpp:116:33: error: could not convert '{<expression error>, y}' from '<brace-enclosed initializer list>' to 'std::pair<long long int, long long int>'
  116 |         return {min(x, r + 1), y};
      |                                 ^
      |                                 |
      |                                 <brace-enclosed initializer list>