제출 #1156578

#제출 시각아이디문제언어결과실행 시간메모리
1156578amongus_pvp나일강 (IOI24_nile)C++17
컴파일 에러
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*)
}

컴파일 시 표준 에러 (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