Submission #883531

# Submission time Handle Problem Language Result Execution time Memory
883531 2023-12-05T11:45:57 Z DAleksa Sparklers (JOI17_sparklers) C++17
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>

using namespace std;

#define int __int128

const int N = 1e5 + 10;
int n, k, t;
int a[N];
__int128 x[N];
set<__int128> L, R;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> t;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = 1e9;
    int ans = r;
    while(l <= r) {
        __int128 mid = (l + r) / 2;
        for(int i = 1; i <= n; i++) x[i] = a[i] - 2LL * mid * i * t;
        L.clear();
        R.clear();
        L.insert(x[k]);
        R.insert(x[k]);
        int i = k, j = k;
        while(true) {
            int change = 0;
            auto it = R.begin();
            if(i > 1) it = R.upper_bound(x[i - 1]);
            while(i > 1 && it != R.begin()) {
                change++;
                i--;
                L.insert(x[i]);
                if(i > 1) it = R.upper_bound(x[i - 1]);
            }
            if(j < n) it = L.lower_bound(x[j + 1]);
            while(j < n && it != L.end()) {
                change++;
                j++;
                R.insert(x[j]);
                if(j < n) it = L.lower_bound(x[j + 1]);
            }
            if(change == 0) break;
        }
        if(i != 1 || j != n) {
            l = mid + 1;
            continue;
        }
        L.clear();
        R.clear();
        L.insert(x[1]);
        R.insert(x[n]);
        if(x[1] < x[n]) {
            l = mid + 1;
            continue;
        }
        i = 1, j = n;
        while(true) {
            int change = 0;
            auto it = R.begin();
            if(i < k) it = R.upper_bound(x[i + 1]);
            while(i < k && it != R.begin()) {
                change++;
                i++;
                L.insert(x[i]);
                if(i < k) it = R.upper_bound(x[i + 1]);
            }
            if(j > k) it = L.lower_bound(x[j - 1]);
            while(j > k && it != L.end()) {
                change++;
                j--;
                R.insert(x[j]);
                if(j > k) it = L.lower_bound(x[j - 1]);
            }
            if(change == 0) break;
        }
        if(i != k || j != k) {
            l = mid + 1;
            continue;
        }
        ans = mid;
        r = mid - 1;
    }
    cout << ans;
    return 0;
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:16:9: error: no match for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and '__int128')
   16 |     cin >> n >> k >> t;
      |     ~~~ ^~ ~
      |     |      |
      |     |      __int128
      |     std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:120:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__istream_type& (*)(std::basic_istream<_CharT, _Traits>::__istream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  120 |       operator>>(__istream_type& (*__pf)(__istream_type&))
      |       ^~~~~~~~
/usr/include/c++/10/istream:120:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: invalid conversion from '__int128' to 'std::basic_istream<char>::__istream_type& (*)(std::basic_istream<char>::__istream_type&)' {aka 'std::basic_istream<char>& (*)(std::basic_istream<char>&)'} [-fpermissive]
   16 |     cin >> n >> k >> t;
      |            ^
      |            |
      |            __int128
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:124:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__ios_type& (*)(std::basic_istream<_CharT, _Traits>::__ios_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>; std::basic_istream<_CharT, _Traits>::__ios_type = std::basic_ios<char>]' (near match)
  124 |       operator>>(__ios_type& (*__pf)(__ios_type&))
      |       ^~~~~~~~
/usr/include/c++/10/istream:124:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: invalid conversion from '__int128' to 'std::basic_istream<char>::__ios_type& (*)(std::basic_istream<char>::__ios_type&)' {aka 'std::basic_ios<char>& (*)(std::basic_ios<char>&)'} [-fpermissive]
   16 |     cin >> n >> k >> t;
      |            ^
      |            |
      |            __int128
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:131:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::ios_base& (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  131 |       operator>>(ios_base& (*__pf)(ios_base&))
      |       ^~~~~~~~
/usr/include/c++/10/istream:131:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: invalid conversion from '__int128' to 'std::ios_base& (*)(std::ios_base&)' [-fpermissive]
   16 |     cin >> n >> k >> t;
      |            ^
      |            |
      |            __int128
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:168:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  168 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:168:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'bool'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:172:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  172 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/10/istream:172:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'short int&' to an rvalue of type 'short int'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:175:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  175 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:175:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'short unsigned int&' to an rvalue of type 'short unsigned int'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:179:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  179 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/10/istream:179:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:182:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  182 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:182:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'unsigned int&' to an rvalue of type 'unsigned int'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:186:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  186 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:186:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'long int&' to an rvalue of type 'long int'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:190:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  190 |       operator>>(unsigned long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:190:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'long unsigned int&' to an rvalue of type 'long unsigned int'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:195:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  195 |       operator>>(long long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:195:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'long long int&' to an rvalue of type 'long long int'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:199:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  199 |       operator>>(unsigned long long& __n)
      |       ^~~~~~~~
/usr/include/c++/10/istream:199:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'long long unsigned int&' to an rvalue of type 'long long unsigned int'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:214:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  214 |       operator>>(float& __f)
      |       ^~~~~~~~
/usr/include/c++/10/istream:214:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'float&' to an rvalue of type 'float'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:218:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  218 |       operator>>(double& __f)
      |       ^~~~~~~~
/usr/include/c++/10/istream:218:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'double&' to an rvalue of type 'double'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:222:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  222 |       operator>>(long double& __f)
      |       ^~~~~~~~
/usr/include/c++/10/istream:222:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: cannot bind non-const lvalue reference of type 'long double&' to an rvalue of type 'long double'
   16 |     cin >> n >> k >> t;
      |            ^
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:235:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]' (near match)
  235 |       operator>>(void*& __p)
      |       ^~~~~~~~
/usr/include/c++/10/istream:235:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: invalid conversion from '__int128' to 'void*' [-fpermissive]
   16 |     cin >> n >> k >> t;
      |            ^
      |            |
      |            __int128
sparklers.cpp:16:12: error: cannot bind rvalue '(void*)((long int)n)' to 'void*&'
In file included from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/istream:259:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__streambuf_type*) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__streambuf_type = std::basic_streambuf<char>]' (near match)
  259 |       operator>>(__streambuf_type* __sb);
      |       ^~~~~~~~
/usr/include/c++/10/istream:259:7: note:   conversion of argument 1 would be ill-formed:
sparklers.cpp:16:12: error: invalid conversion from '__int128' to 'std::basic_istream<char>::__streambuf_type*' {aka 'std::basic_streambuf<char>*'} [-fpermissive]
   16 |     cin >> n >> k >> t;
      |            ^
      |            |
      |            __int128
sparklers.cpp:16:9: note: candidate: 'operator>>(int, __int128)' (built-in)
   16 |     cin >> n >> k >> t;
      |     ~~~~^~~~
sparklers.cpp:16:9: note:   no known conversion for argument 1 from 'std::istream' {aka 'std::basic_istream<char>'} to 'int'
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:45,
                 from sparklers.cpp:1:
/usr/include/c++/10/cstddef:130:5: note: candidate: 'template<class _IntegerType> constexpr std::__byte_op_t<_IntegerType> std::operator>>(std::byte, _IntegerType)'
  130 |     operator>>(byte __b, _IntegerType __shift) noexcept
      |     ^~~~~~~~
/usr/include/c++/10/cstddef:130:5: note:   template argument deduction/substitution failed:
sparklers.cpp:16:5: note:   cannot convert 'std::cin' (type 'std::istream' {aka 'std::basic_istream<char>'}) to type 'std::byte'
   16 |     cin >> n >> k >> t;
      |     ^~~
In file included from /usr/include/c++/10/string:56,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sparklers.cpp:1:
/usr/include/c++/10/bits/basic_string.tcc:1476:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::basic_istream<_CharT, _Traits>& std::operator>>(std::basic_istream<_CharT, _Traits>&, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 1476 |     operator>>(basic_istream<_CharT, _Traits>& __in,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.tcc:1476:5: note:   template argument deduction/substitution failed:
sparklers.cpp:16:12: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and '__int128'
   16 |     cin >>