Submission #949712

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
949712	2024-03-19T15:23:26 Z	smartmonky	Painting Walls (APIO20_paint)	C++17	Compilation error	0 ms	0 KB

paint

#include "paint.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
typedef pair<int, int> T;
const int oo = 1e9+7, K = 30;
 
struct Tree{
	vector<int>tab;
	int size = 1;
 
	Tree(int n){
		while (size < n) size*=2;
		tab.assign(2*size, oo);
	}
	
	void update(int x, int v){
		x += size;
		tab[x] = v;
		while (x){
			x/=2;
			tab[x] = min(tab[2*x], tab[2*x+1]);
		}
	}
 
	int query(int l, int r){
		int ans = oo;
		for (l += size-1, r += size+1; r-l>1; l/=2, r/=2){
			if (!(l&1)) ans = min(ans, tab[l+1]);
			if (r&1) ans = min(ans, tab[r-1]);
		}
		return ans;
	}
};
 
int minimumInstructions(int n, int m, int k, vector<int>c, vector<int>len, vector<vector<int>>what){
	vector<vector<int>>who(k);
	for (int i = 0; i<m; i++){
		for (auto col: what[i]){
			who[col].emplace_back(i);
		}
	}
	for (int i = 0; i<k; i++){
		debug(i, who[i]);
	}
	vector<int>dp;
	vector<int>ok(n);
	for (int i = 0; i<n; i++){
		int s = (int)who[c[i]].size();
		vector<int>new_dp(s, 1);
		auto &t = who[c[i]];
		if (t.empty()) return -1;
		if (i){
			//przejscia jakies
			int ptr = -1;
			for (int j = 0; j<s; j++){
				while (ptr+1 < (int)who[c[i-1]].size() && who[c[i-1]][ptr+1] < t[j]) ptr++;
				if (ptr >= 0 && t[j]-who[c[i-1]][ptr] == 1) new_dp[j] = max(new_dp[j], dp[ptr]+1);
			}
		}
		dp.swap(new_dp);
		int mx = *max_element(dp.begin(), dp.end());
		if (mx >= m){
			ok[i] = 1;
		}
	}
	debug(ok);
	dp.assign(n, -1);
	if (!ok[m-1]) return -1;
	dp[m-1] = 1;
	Tree t(n+1);
	t.update(m-1, dp[m-1]);
	for (int i = m; i<n; i++){
		if (!ok[i]) continue;
		dp[i] = t.query(i-m, i-1)+1;
		t.update(i, dp[i]);
	}
	debug(dp);
	if (dp[n-1] < 0 || dp[n-1] > n) return -1;
	return dp[n-1];
}

Compilation message

paint.cpp: In function 'void __print(int)':
paint.cpp:5:22: error: 'cerr' was not declared in this scope
    5 | void __print(int x) {cerr << x;}
      |                      ^~~~
paint.cpp:2:1: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
    1 | #include "paint.h"
  +++ |+#include <iostream>
    2 | #pragma GCC optimize("O3", "unroll-loops")
paint.cpp: In function 'void __print(long long int)':
paint.cpp:6:28: error: 'cerr' was not declared in this scope
    6 | void __print(long long x) {cerr << x;}
      |                            ^~~~
paint.cpp:6:28: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
paint.cpp: In function 'void __print(long double)':
paint.cpp:7:30: error: 'cerr' was not declared in this scope
    7 | void __print(long double x) {cerr << x;}
      |                              ^~~~
paint.cpp:7:30: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
paint.cpp: In function 'void __print(char)':
paint.cpp:8:23: error: 'cerr' was not declared in this scope
    8 | void __print(char x) {cerr << "'" << x << "'";}
      |                       ^~~~
paint.cpp:8:23: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
paint.cpp: In function 'void __print(const char*)':
paint.cpp:9:30: error: 'cerr' was not declared in this scope
    9 | void __print(const char *x) {cerr << '"' << x << '"';}
      |                              ^~~~
paint.cpp:9:30: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
paint.cpp: At global scope:
paint.cpp:10:20: error: 'string' does not name a type
   10 | void __print(const string &x) {cerr << '"' << x << '"';}
      |                    ^~~~~~
paint.cpp: In function 'void __print(const int&)':
paint.cpp:10:32: error: 'cerr' was not declared in this scope
   10 | void __print(const string &x) {cerr << '"' << x << '"';}
      |                                ^~~~
paint.cpp:10:32: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
paint.cpp: In function 'void __print(bool)':
paint.cpp:11:23: error: 'cerr' was not declared in this scope
   11 | void __print(bool x) {cerr << (x ? "true" : "false");}
      |                       ^~~~
paint.cpp:11:23: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
paint.cpp: In function 'void __print(const std::pair<_T1, _T2>&)':
paint.cpp:14:36: error: 'cerr' was not declared in this scope
   14 | void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
      |                                    ^~~~
paint.cpp:14:36: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
paint.cpp: In function 'void __print(const T&)':
paint.cpp:16:38: error: 'cerr' was not declared in this scope
   16 | void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
      |                                      ^~~~
paint.cpp:16:38: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
paint.cpp: In function 'void _print()':
paint.cpp:17:16: error: 'cerr' was not declared in this scope
   17 | void _print() {cerr << "]\n";}
      |                ^~~~
paint.cpp:17:16: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
paint.cpp: In function 'void _print(T, V ...)':
paint.cpp:19:57: error: 'cerr' was not declared in this scope
   19 | void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
      |                                                         ^~~~
paint.cpp:19:57: note: 'std::cerr' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:83:13: error: 'max_element' was not declared in this scope
   83 |   int mx = *max_element(dp.begin(), dp.end());
      |             ^~~~~~~~~~~