제출 #1252718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252718		comgaTramAnh	축제 (IOI25_festival)	C++20	컴파일 에러	0 ms	0 KiB

festival

#include <bits/stdc++.h> 
//#include "festival.h"

using namespace std;
std::vector <int> max_coupons(int A, std::vector <int> P, std::vector <int> T) {
  auto compare = [&](int i, int j) {
    std::pair <int, int> a = std::make_pair(P[i], T[i]); 
    std::pair <int, int> b = std::make_pair(P[j], T[j]); 
    return (1LL * a.first * a.second * b.second + 1LL * b.first * b.second < 1LL * b.first * a.second * b.second + 1LL * a.first * a.second);
  };
  auto compareOne = [&](int i, int j) {
    return P[i] < P[j]; 
  };
  std::vector <int> ones, other;
  for (int i = 0; i < (int) T.size(); i++) {
    if (T[i] == 1) {
      ones.push_back(i); 
    }
    else {
      other.push_back(i); 
    }
  } 
  std::sort(ones.begin(), ones.end(), compareOne); 
  std::sort(other.begin(), other.end(), compare); 
  std::cout << std::endl;
  int n = (int) ones.size(); 
  int numbT = std::min(30, (int) other.size());
  std::vector <long double> mul(numbT + 1); 
  mul[0] = 1LL; 
  for (int i = 1; i <= numbT; i++) {
    mul[i] = (long double) mul[i - 1] * T[other[i - 1]]; 
  }
  const double inf = -1.0000; 
  std::vector <std::vector <std::pair <int, int>>> trace(n + 1); 
  std::vector <std::vector <double>> f(n + 1);
  for (int i = 0; i <= n; i++) {
    f[i].resize(numbT + 1, inf); 
    trace[i].resize(numbT + 1, std::make_pair(-1, -1)); 
  }        
  const long double eps = 1e-9; 
  f[0][0] = (long double) A;             
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= numbT; j++) {
      if (f[i][j] < 0.0) {
        continue; 
      }
      if (i < n && f[i][j] + eps >= (long double) P[ones[i]] / mul[j]) {
        if (f[i + 1][j] < std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j])) {
          f[i + 1][j] = std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j]);
          trace[i + 1][j] = std::make_pair(i, j); 
        } 
      }
      if (j < numbT && f[i][j] + eps >= (long double) P[other[j]] / mul[j]) {
        if (f[i][j + 1] < std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j])) {
          f[i][j + 1] = std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j]);
          trace[i][j + 1] = std::make_pair(i, j);  
        } 
      }    
    }
  }
  std::vector <int> ret;
  int maxNumb = -1; 
  int posi = -1, posj = -1; 
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= numbT; j++) {
      if (maxNumb < i + j && f[i][j] != inf) {
        maxNumb = i + j;
        posi = i;
        posj = j; 
      }
    }
  }                                      
  while (posi > 0 || posj > 0) {
    std::pair <int, int> prev = trace[posi][posj];                 
    if (prev.second == posj) {
      ret.push_back(ones[prev.first]); 
      posi = prev.first; 
    }
    else {
      ret.push_back(other[prev.second]); 
      posi = prev.first; 
      posj = prev.second; 
    }
  }
  std::reverse(ret.begin(), ret.end()); 
  return ret;  
}

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

festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:48:35: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<double>, double>::value_type&, long double)'
   48 |         if (f[i + 1][j] < std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j])) {
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from festival.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
festival.cpp:48:35: note:   deduced conflicting types for parameter 'const _Tp' ('double' and 'long double')
   48 |         if (f[i + 1][j] < std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j])) {
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from festival.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
festival.cpp:48:35: note:   deduced conflicting types for parameter 'const _Tp' ('double' and 'long double')
   48 |         if (f[i + 1][j] < std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j])) {
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
festival.cpp:48:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'double'
   48 |         if (f[i + 1][j] < std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j])) {
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
festival.cpp:48:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'double'
   48 |         if (f[i + 1][j] < std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j])) {
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
festival.cpp:49:33: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<double>, double>::value_type&, long double)'
   49 |           f[i + 1][j] = std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j]);
      |                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from festival.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
festival.cpp:49:33: note:   deduced conflicting types for parameter 'const _Tp' ('double' and 'long double')
   49 |           f[i + 1][j] = std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j]);
      |                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from festival.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
festival.cpp:49:33: note:   deduced conflicting types for parameter 'const _Tp' ('double' and 'long double')
   49 |           f[i + 1][j] = std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j]);
      |                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
festival.cpp:49:33: note:   mismatched types 'std::initializer_list<_Tp>' and 'double'
   49 |           f[i + 1][j] = std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j]);
      |                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
festival.cpp:49:33: note:   mismatched types 'std::initializer_list<_Tp>' and 'double'
   49 |           f[i + 1][j] = std::max(f[i + 1][j], f[i][j] - (long double) P[ones[i]] / mul[j]);
      |                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
festival.cpp:54:35: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<double>, double>::value_type&, long double)'
   54 |         if (f[i][j + 1] < std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j])) {
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from festival.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
festival.cpp:54:35: note:   deduced conflicting types for parameter 'const _Tp' ('double' and 'long double')
   54 |         if (f[i][j + 1] < std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j])) {
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from festival.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
festival.cpp:54:35: note:   deduced conflicting types for parameter 'const _Tp' ('double' and 'long double')
   54 |         if (f[i][j + 1] < std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j])) {
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
festival.cpp:54:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'double'
   54 |         if (f[i][j + 1] < std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j])) {
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
festival.cpp:54:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'double'
   54 |         if (f[i][j + 1] < std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j])) {
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
festival.cpp:55:33: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<double>, double>::value_type&, long double)'
   55 |           f[i][j + 1] = std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j]);
      |                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from festival.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
festival.cpp:55:33: note:   deduced conflicting types for parameter 'const _Tp' ('double' and 'long double')
   55 |           f[i][j + 1] = std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j]);
      |                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from festival.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
festival.cpp:55:33: note:   deduced conflicting types for parameter 'const _Tp' ('double' and 'long double')
   55 |           f[i][j + 1] = std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j]);
      |                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
festival.cpp:55:33: note:   mismatched types 'std::initializer_list<_Tp>' and 'double'
   55 |           f[i][j + 1] = std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j]);
      |                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
festival.cpp:55:33: note:   mismatched types 'std::initializer_list<_Tp>' and 'double'
   55 |           f[i][j + 1] = std::max(f[i][j + 1], f[i][j] - (long double) P[other[j]] / mul[j]);
      |                         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~