Submission #1156578

#TimeUsernameProblemLanguageResultExecution timeMemory
1156578amongus_pvpNile (IOI24_nile)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; using lint = long long using pi = array<lint, 2> #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() // typical conventions #define cr(v, n) (v).clear(), (v).resize(n); // we love #define here ;D const int MAXN = 100005; const int MAXT = 270000; // we need to define some structs first, segment tree is the most important struct matrix { lint A[3][3]; matrix() { memset(A, 0x3f, sizeof(A)); A[0][0] = A[1][1] = A[2][2] = 0; // some initialising } matrix operator+(const matrix &m){ matrix ret; memset(ret.A, 0x3f, sizeof(ret.A)); for (int i = 0; i<3; i++){ for (int j = 0; j < 3; j++){ for (int k = 0; k < 3; k++){ ret.A[i][k] = min(A[i][j] + m.A[j][k], ret.A[i][k]); } } } return ret; } } M[MAXN]; // now to write the segtree struct segtree { int lim; matrix tree[MAXT]; void init(int n){ for (lim = 1; lim <= n; lim <<= 1);// fun operator usage/ bitwise shift for (int i = 0; i < n; i++){ tree[i + lim] = M[i]; } for (int i = lim - 1; i; i--){ tree[i] = tree[2 * i] + tree[2 * i + 1]; } } // need an update function void upd(int x, matrix v){ x += lim; tree[x] = v; while (x > 1){ x >>= 1; tree[x] = tree[2 * x] + tree[2 * x + 1]; } } } seg; // all done with this :D // now for the hard part :skull: /* IMO this problem is way too hard for a problem 1, to be fair im really bad at info but still */ vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){ int n = sz(W); vector<array<lint, 3>> a(n); for (int i = 0; i < n; i++){ a[i] = {W[i], A[i], B[i]}; } sort(all(a)); vector<array<int, 3>> events; for (int i = 1; i < n; i++){ events.push_back({int(a[i][0] - a[i-1][0]), i-1, i}); if (i > 1){ events.push_back({int(a[i][0] - a[i - 2][0], i - 2, i)}); } } sort(all(events)); // dp table time ;D // di = di-1 + ai-1.1 // = di-2 ai-1.2 + ai-2.2 // = di-3 + ai-1.2 + ai-3.2 + ai-1.1 for (int i = 0; i < n; i++){ memset(M[i].A, 0x3f, sizeof(M[i].A)); M[i].A[0][0] = a[i][1]; M[i].A[1][0] = M[i].A[2][1] = 0; } vector<pi> ans; seg.init(n); ans.push_back({0, seg.tree[1].A[0][0]}); // taking a break for a second // i might be cooked asl for (auto &[v, l, r] : events){ if (r - l == 2){ M[l].A[0][2] = a[l][2] + a[r][2] + a[l+1][1]; } else { M[l].A[0][1] = a[l][2] + a[r][2]; } seg.upd(l, M[l]); ans.push_back({v, seg.tree[1].A[0][0]}); } vector<lint> dap(sz(E)); vector<pi> queries; for (int i = 0; i < sz(E); i++){ queries.push_back({E[i], i}); } sort(all(queries)); int j = 0; for (auto &[k, idx] : queries) { while (j < sz(ans) && ans[j][0] <= k){ j++; } dap[idx] = ans[j - 1][1]; } return dap; // dap me up ma boy (*finishes problem*) }

Compilation message (stderr)

nile.cpp:3:23: error: expected ';' before 'using'
    3 | using lint = long long
      |                       ^
      |                       ;
    4 | using pi = array<lint, 2>
      | ~~~~~                  
nile.cpp:15:9: error: 'lint' does not name a type; did you mean 'uint'?
   15 |         lint A[3][3];
      |         ^~~~
      |         uint
nile.cpp: In constructor 'matrix::matrix()':
nile.cpp:17:24: error: 'A' was not declared in this scope
   17 |                 memset(A, 0x3f, sizeof(A));
      |                        ^
nile.cpp: In member function 'matrix matrix::operator+(const matrix&)':
nile.cpp:23:28: error: 'struct matrix' has no member named 'A'
   23 |                 memset(ret.A, 0x3f, sizeof(ret.A));
      |                            ^
nile.cpp:23:48: error: 'struct matrix' has no member named 'A'
   23 |                 memset(ret.A, 0x3f, sizeof(ret.A));
      |                                                ^
nile.cpp:27:45: error: 'struct matrix' has no member named 'A'
   27 |                                         ret.A[i][k] = min(A[i][j] + m.A[j][k], ret.A[i][k]);
      |                                             ^
nile.cpp:27:59: error: 'A' was not declared in this scope
   27 |                                         ret.A[i][k] = min(A[i][j] + m.A[j][k], ret.A[i][k]);
      |                                                           ^
nile.cpp:27:71: error: 'const struct matrix' has no member named 'A'
   27 |                                         ret.A[i][k] = min(A[i][j] + m.A[j][k], ret.A[i][k]);
      |                                                                       ^
nile.cpp:27:84: error: 'struct matrix' has no member named 'A'
   27 |                                         ret.A[i][k] = min(A[i][j] + m.A[j][k], ret.A[i][k]);
      |                                                                                    ^
nile.cpp: At global scope:
nile.cpp:33:5: error: 'MAXN' was not declared in this scope; did you mean 'MAXT'?
   33 | } M[MAXN];
      |     ^~~~
      |     MAXT
nile.cpp: In member function 'void segtree::init(int)':
nile.cpp:43:41: error: 'M' was not declared in this scope
   43 |                         tree[i + lim] = M[i];
      |                                         ^
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:70:22: error: 'lint' was not declared in this scope; did you mean 'uint'?
   70 |         vector<array<lint, 3>> a(n);
      |                      ^~~~
      |                      uint
nile.cpp:70:28: error: template argument 1 is invalid
   70 |         vector<array<lint, 3>> a(n);
      |                            ^
nile.cpp:70:29: error: template argument 1 is invalid
   70 |         vector<array<lint, 3>> a(n);
      |                             ^~
nile.cpp:70:29: error: template argument 2 is invalid
nile.cpp:72:18: error: invalid types 'int[int]' for array subscript
   72 |                 a[i] = {W[i], A[i], B[i]};
      |                  ^
nile.cpp:6:20: error: request for member 'begin' in 'a', which is of non-class type 'int'
    6 | #define all(v) (v).begin(), (v).end() // typical conventions
      |                    ^~~~~
nile.cpp:74:14: note: in expansion of macro 'all'
   74 |         sort(all(a));
      |              ^~~
nile.cpp:6:33: error: request for member 'end' in 'a', which is of non-class type 'int'
    6 | #define all(v) (v).begin(), (v).end() // typical conventions
      |                                 ^~~
nile.cpp:74:14: note: in expansion of macro 'all'
   74 |         sort(all(a));
      |              ^~~
nile.cpp:78:40: error: invalid types 'int[int]' for array subscript
   78 |                 events.push_back({int(a[i][0] - a[i-1][0]), i-1, i});
      |                                        ^
nile.cpp:78:50: error: invalid types 'int[int]' for array subscript
   78 |                 events.push_back({int(a[i][0] - a[i-1][0]), i-1, i});
      |                                                  ^
nile.cpp:78:33: error: no matching function for call to 'std::vector<std::array<int, 3> >::push_back(<brace-enclosed initializer list>)'
   78 |                 events.push_back({int(a[i][0] - a[i-1][0]), i-1, i});
      |                 ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::array<int, 3>; _Alloc = std::allocator<std::array<int, 3> >; std::vector<_Tp, _Alloc>::value_type = std::array<int, 3>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<int, 3>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::array<int, 3>; _Alloc = std::allocator<std::array<int, 3> >; std::vector<_Tp, _Alloc>::value_type = std::array<int, 3>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::array<int, 3> >::value_type&&' {aka 'std::array<int, 3>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
nile.cpp:80:48: error: invalid types 'int[int]' for array subscript
   80 |                         events.push_back({int(a[i][0] - a[i - 2][0], i - 2, i)});
      |                                                ^
nile.cpp:80:58: error: invalid types 'int[int]' for array subscript
   80 |                         events.push_back({int(a[i][0] - a[i - 2][0], i - 2, i)});
      |                                                          ^
nile.cpp:80:78: error: expression list treated as compound expression in functional cast [-fpermissive]
   80 |                         events.push_back({int(a[i][0] - a[i - 2][0], i - 2, i)});
      |                                                                              ^
nile.cpp:80:41: error: no matching function for call to 'std::vector<std::array<int, 3> >::push_back(<brace-enclosed initializer list>)'
   80 |                         events.push_back({int(a[i][0] - a[i - 2][0], i - 2, i)});
      |                         ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::array<int, 3>; _Alloc = std::allocator<std::array<int, 3> >; std::vector<_Tp, _Alloc>::value_type = std::array<int, 3>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<int, 3>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::array<int, 3>; _Alloc = std::allocator<std::array<int, 3> >; std::vector<_Tp, _Alloc>::value_type = std::array<int, 3>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::array<int, 3> >::value_type&&' {aka 'std::array<int, 3>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
nile.cpp:92:24: error: 'M' was not declared in this scope
   92 |                 memset(M[i].A, 0x3f, sizeof(M[i].A));
      |                        ^
nile.cpp:93:33: error: invalid types 'int[int]' for array subscript
   93 |                 M[i].A[0][0] = a[i][1];
      |                                 ^
nile.cpp:97:16: error: 'pi' was not declared in this scope
   97 |         vector<pi> ans;
      |                ^~
nile.cpp:97:18: error: template argument 1 is invalid
   97 |         vector<pi> ans;
      |                  ^
nile.cpp:97:18: error: template argument 2 is invalid
nile.cpp:101:13: error: request for member 'push_back' in 'ans', which is of non-class type 'int'
  101 |         ans.push_back({0, seg.tree[1].A[0][0]});
      |             ^~~~~~~~~
nile.cpp:101:39: error: 'struct matrix' has no member named 'A'
  101 |         ans.push_back({0, seg.tree[1].A[0][0]});
      |                                       ^
nile.cpp:108:25: error: 'M' was not declared in this scope
  108 |                         M[l].A[0][2] = a[l][2] + a[r][2] + a[l+1][1];
      |                         ^
nile.cpp:108:41: error: invalid types 'int[std::tuple_element<1, std::array<int, 3> >::type {aka int}]' for array subscript
  108 |                         M[l].A[0][2] = a[l][2] + a[r][2] + a[l+1][1];
      |                                         ^
nile.cpp:108:51: error: invalid types 'int[std::tuple_element<2, std::array<int, 3> >::type {aka int}]' for array subscript
  108 |                         M[l].A[0][2] = a[l][2] + a[r][2] + a[l+1][1];
      |                                                   ^
nile.cpp:108:61: error: invalid types 'int[std::tuple_element<1, std::array<int, 3> >::type {aka int}]' for array subscript
  108 |                         M[l].A[0][2] = a[l][2] + a[r][2] + a[l+1][1];
      |                                                             ^
nile.cpp:111:25: error: 'M' was not declared in this scope
  111 |                         M[l].A[0][1] = a[l][2] + a[r][2];
      |                         ^
nile.cpp:111:41: error: invalid types 'int[std::tuple_element<1, std::array<int, 3> >::type {aka int}]' for array subscript
  111 |                         M[l].A[0][1] = a[l][2] + a[r][2];
      |                                         ^
nile.cpp:111:51: error: invalid types 'int[std::tuple_element<2, std::array<int, 3> >::type {aka int}]' for array subscript
  111 |                         M[l].A[0][1] = a[l][2] + a[r][2];
      |                                                   ^
nile.cpp:114:28: error: 'M' was not declared in this scope
  114 |                 seg.upd(l, M[l]);
      |                            ^
nile.cpp:115:21: error: request for member 'push_back' in 'ans', which is of non-class type 'int'
  115 |                 ans.push_back({v, seg.tree[1].A[0][0]});
      |                     ^~~~~~~~~
nile.cpp:115:47: error: 'struct matrix' has no member named 'A'
  115 |                 ans.push_back({v, seg.tree[1].A[0][0]});
      |                                               ^
nile.cpp:118:20: error: template argument 2 is invalid
  118 |         vector<lint> dap(sz(E));
      |                    ^
nile.cpp:119:18: error: template argument 2 is invalid
  119 |         vector<pi> queries;
      |                  ^
nile.cpp:122:25: error: request for member 'push_back' in 'queries', which is of non-class type 'int'
  122 |                 queries.push_back({E[i], i});
      |                         ^~~~~~~~~
nile.cpp:6:20: error: request for member 'begin' in 'queries', which is of non-class type 'int'
    6 | #define all(v) (v).begin(), (v).end() // typical conventions
      |                    ^~~~~
nile.cpp:125:14: note: in expansion of macro 'all'
  125 |         sort(all(queries));
      |              ^~~
nile.cpp:6:33: error: request for member 'end' in 'queries', which is of non-class type 'int'
    6 | #define all(v) (v).begin(), (v).end() // typical conventions
      |                                 ^~~
nile.cpp:125:14: note: in expansion of macro 'all'
  125 |         sort(all(queries));
      |              ^~~
nile.cpp:129:31: error: 'begin' was not declared in this scope
  129 |         for (auto &[k, idx] : queries) {
      |                               ^~~~~~~
nile.cpp:129:31: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
                 from nile.cpp:1:
/usr/include/c++/11/valarray:1228:5: note:   'std::begin'
 1228 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
In file included from /usr/include/c++/11/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:129,
                 from nile.cpp:1:
/usr/include/c++/11/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
nile.cpp:129:31: error: 'end' was not declared in this scope
  129 |         for (auto &[k, idx] : queries) {
      |                               ^~~~~~~
nile.cpp:129:31: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
                 from nile.cpp:1:
/usr/include/c++/11/valarray:1255:5: note:   'std::end'
 1255 |     end(const valarray<_Tp>& __va) noexcept
      |     ^~~
In file included from /usr/include/c++/11/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:129,
                 from nile.cpp:1:
/usr/include/c++/11/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
nile.cpp:5:25: error: request for member 'size' in 'ans', which is of non-class type 'int'
    5 | #define sz(v) ((int)(v).size())
      |                         ^~~~
nile.cpp:130:28: note: in expansion of macro 'sz'
  130 |                 while (j < sz(ans) && ans[j][0] <= k){
      |                            ^~
nile.cpp:130:42: error: invalid types 'int[int]' for array subscript
  130 |                 while (j < sz(ans) && ans[j][0] <= k){
      |                                          ^
nile.cpp:133:31: error: invalid types 'int[int]' for array subscript
  133 |                 dap[idx] = ans[j - 1][1];
      |                               ^
nile.cpp:135:16: error: could not convert 'dap' from 'int' to 'std::vector<long long int>'
  135 |         return dap; // dap me up ma boy (*finishes problem*)
      |                ^~~
      |                |
      |                int