제출 #1088763

#제출 시각아이디문제언어결과실행 시간메모리
1088763alexz1205Aliens (IOI16_aliens)C++14
컴파일 에러
0 ms0 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long int lint; typedef __int128 llint; typedef long double ldoub; const int N = 1e5; llint PREC = 1e10; array<llint, 2> ransDat[N]; array<llint, 2> rans[N]; int sizeR = 0; llint dp[N+1]; int dp2[N+1]; llint slope(llint sl1p1, llint sl1p2, llint sl2p1, llint sl2p2){ llint a = sl1p1, b = sl1p2, c = sl2p1, d = sl2p2; for (int x = 0; x < 200; x ++){ llint k1 = sl1p1 / sl1p2; llint k2 = sl2p1 / sl2p2; if (k1 != k2){ return k1 - k2; } sl1p1 %= sl1p2; sl2p1 %= sl2p2; sl1p1 <<= 1; sl2p1 <<= 1; } return 0; } void calc(llint adjust){ vector<array<llint, 3>> hull; hull.push_back({rans[0][0], -rans[0][0] * rans[0][0], 0}); for (int x = 0; x < rans.size(); x ++){ llint s = -2 * rans[x][1]; llint B = rans[x][1] * rans[x][1]; int a = 1, b = hull.size()-1; while (a <= b){ int mid = (b-a+1)/2 + a; llint slp1 = (hull[mid][1] - hull[mid-1][1]); llint slp2 = (hull[mid][0] - hull[mid-1][0]); if (slope(slp1, slp2, s, (llint)1) < 0){ b = mid-1; }else { a = mid+1; } } int r = a-1; dp[x] = -hull[r][1] + B + hull[r][0] * s + adjust; dp2[x] = hull[r][2] + 1; if (x == rans.size()-1) continue; llint right = min(rans[x][1], rans[x+1][0]); array<llint, 3> p = {rans[x+1][0], -dp[x] + (rans[x][1] - right) * (rans[x][1] - right) - rans[x+1][0] * rans[x+1][0], dp2[x]}; while (hull.size() > 1){ llint sl1p1 = (p[1] - hull[hull.size()-2][1]); llint sl1p2 = (p[0] - hull[hull.size()-2][0]); llint sl2p1 = (hull[hull.size()-1][1] - hull[hull.size()-2][1]); llint sl2p2 = (hull[hull.size()-1][0] - hull[hull.size()-2][0]); if (slope(sl1p1, sl1p2, sl2p1, sl2p2) >= 0){ hull.pop_back(); }else { break; } } hull.push_back(p); } } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { ::n = n; ::m = m; PREC = 10*m; for (int x = 0; x < n; x ++){ ransDat[x][0] = PREC*min(r[x], c[x]); ransDat[x][1] = PREC*(max(r[x], c[x]) + 1); } sort(ransDat, ransDat+n, [](array<llint, 2> a, array<llint, 2> b){return (a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]);}); { llint ma = 0; for (int x = 0; x < n; x ++){ if (ma >= ransDat[x][1]){ continue; } ma = ransDat[x][1]; rans[sizeR++] = ransDat[x]; } } k = min(k, (int)rans.size()); llint a = -(llint)1e12 * PREC * PREC, b = (llint)1e12 * PREC * PREC; pair<llint, int> up = {1e12 * PREC*PREC, -1}; pair<llint, int> low = {1e12 * PREC*PREC, -1}; while (a <= b){ llint mid = (b-a+1)/2 + a; llint v = mid; calc(v); if (dp2[rans.size()-1] == k){ llint val = dp[rans.size()-1]; val -= k*v; val /= PREC; val /= PREC; return (lint)val; } if (dp2[rans.size()-1] < k){ llint val = dp[rans.size()-1]; val -= dp2[rans.size()-1]*v; val /= PREC; val /= PREC; up = {val, dp2[rans.size()-1]}; b = mid-1; }else { llint val = dp[rans.size()-1]; val -= dp2[rans.size()-1]*v; val /= PREC; val /= PREC; low = {val, dp2[rans.size()-1]}; a = mid+1; } } llint best = ((up.first-low.first) * (k-low.second))/(up.second - low.second) + low.first; return best; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'llint slope(llint, llint, llint, llint)':
aliens.cpp:20:8: warning: unused variable 'a' [-Wunused-variable]
   20 |  llint a = sl1p1, b = sl1p2, c = sl2p1, d = sl2p2;
      |        ^
aliens.cpp:20:19: warning: unused variable 'b' [-Wunused-variable]
   20 |  llint a = sl1p1, b = sl1p2, c = sl2p1, d = sl2p2;
      |                   ^
aliens.cpp:20:30: warning: unused variable 'c' [-Wunused-variable]
   20 |  llint a = sl1p1, b = sl1p2, c = sl2p1, d = sl2p2;
      |                              ^
aliens.cpp:20:41: warning: unused variable 'd' [-Wunused-variable]
   20 |  llint a = sl1p1, b = sl1p2, c = sl2p1, d = sl2p2;
      |                                         ^
aliens.cpp: In function 'void calc(llint)':
aliens.cpp:38:27: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
   38 |  for (int x = 0; x < rans.size(); x ++){
      |                           ^~~~
aliens.cpp:57:17: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
   57 |   if (x == rans.size()-1) continue;
      |                 ^~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:79:4: error: '::n' has not been declared
   79 |  ::n = n;
      |    ^
aliens.cpp:80:4: error: '::m' has not been declared
   80 |  ::m = m;
      |    ^
aliens.cpp:99:23: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
   99 |  k = min(k, (int)rans.size());
      |                       ^~~~
aliens.cpp:109:16: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
  109 |   if (dp2[rans.size()-1] == k){
      |                ^~~~
aliens.cpp:110:24: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
  110 |    llint val = dp[rans.size()-1];
      |                        ^~~~
aliens.cpp:116:16: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
  116 |   if (dp2[rans.size()-1] < k){
      |                ^~~~
aliens.cpp:117:24: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
  117 |    llint val = dp[rans.size()-1];
      |                        ^~~~
aliens.cpp:118:20: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
  118 |    val -= dp2[rans.size()-1]*v;
      |                    ^~~~
aliens.cpp:121:24: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
  121 |    up = {val, dp2[rans.size()-1]};
      |                        ^~~~
aliens.cpp:121:33: error: no match for 'operator=' (operand types are 'std::pair<__int128, int>' and '<brace-enclosed initializer list>')
  121 |    up = {val, dp2[rans.size()-1]};
      |                                 ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = __int128; _T2 = int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<__int128, int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<__int128, int>&, const std::__nonesuch&>::type' {aka 'const std::pair<__int128, int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = __int128; _T2 = int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<__int128, int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<__int128, int>&&, std::__nonesuch&&>::type' {aka 'std::pair<__int128, int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = __int128; _T2 = int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
aliens.cpp:121:33: note:   couldn't deduce template parameter '_U1'
  121 |    up = {val, dp2[rans.size()-1]};
      |                                 ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = __int128; _T2 = int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
aliens.cpp:121:33: note:   couldn't deduce template parameter '_U1'
  121 |    up = {val, dp2[rans.size()-1]};
      |                                 ^
aliens.cpp:124:24: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
  124 |    llint val = dp[rans.size()-1];
      |                        ^~~~
aliens.cpp:125:20: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
  125 |    val -= dp2[rans.size()-1]*v;
      |                    ^~~~
aliens.cpp:128:25: error: request for member 'size' in 'rans', which is of non-class type 'std::array<__int128, 2> [100000]'
  128 |    low = {val, dp2[rans.size()-1]};
      |                         ^~~~
aliens.cpp:128:34: error: no match for 'operator=' (operand types are 'std::pair<__int128, int>' and '<brace-enclosed initializer list>')
  128 |    low = {val, dp2[rans.size()-1]};
      |                                  ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = __int128; _T2 = int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<__int128, int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<__int128, int>&, const std::__nonesuch&>::type' {aka 'const std::pair<__int128, int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = __int128; _T2 = int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<__int128, int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<__int128, int>&&, std::__nonesuch&&>::type' {aka 'std::pair<__int128, int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = __int128; _T2 = int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
aliens.cpp:128:34: note:   couldn't deduce template parameter '_U1'
  128 |    low = {val, dp2[rans.size()-1]};
      |                                  ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = __int128; _T2 = int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
aliens.cpp:128:34: note:   couldn't deduce template parameter '_U1'
  128 |    low = {val, dp2[rans.size()-1]};
      |                                  ^