Submission #861110

#	Time	Username	Problem	Language	Result	Execution time	Memory
861110		lovrot	Teams (CEOI11_tea)	C++17	0 / 100	2564 ms	28200 KiB

tea

#include <cstdio> 
#include <algorithm> 
#include <queue>
#include <stack> 
#include <deque> 
#include <vector> 

#define X first
#define Y second

using namespace std;

typedef pair<int, int> pii;

const int N = 1e6 + 10;
const int oo = 2e9; 

template <typename T> 
struct mono_stack {
	stack<T> S; 
	bool empty() const { return S.empty(); }
	void push(T x) {
		while(!S.empty() && S.top() < x) S.pop(); 
		S.push(x); 
	}
	void clear() {
		while(!S.empty()) S.pop();
	}
	void pop(T x) {
		if(!S.empty() && S.top() == x) S.pop();
	}
	T top() {
		if(S.empty()) return T();
		return S.top(); 
	}
};

template <typename T> 
struct mono_deque {	
	mono_stack<T> L, R;
	deque<T> D;
	bool empty() const { return D.empty(); }
	void build() {
		L.clear(); 
		R.clear(); 
		for(int i = (D.size() - 1) / 2; i >= 0; --i) L.push(D[i]); 
		for(int i = (D.size() - 1) / 2 + 1; i < D.size(); ++i) R.push(D[i]); 
	}
	void pop_front() {
		if(D.empty()) return;
		T x = D.front();
		D.pop_front(); 
		if(L.empty()) this->build();
		else L.pop(x);
	}
	void pop_back() {
		if(D.empty()) return;
		T x = D.back();
		D.pop_back(); 
		if(R.empty()) this->build();
		else R.pop(x);
	}
	void push_front(T x) { 
		D.push_front(x);
		L.push(x); 
	}
	void push_back(T x) { 
		D.push_back(x);
		R.push(x);
	}
	T max() { 
		T a = L.top(), b = R.top();
		return a < b ? b : a;
	}
	void print() {
		for(int i = 0; i < D.size(); ++i) printf("%d%c", D[i].X, " \n"[i == (D.size()) - 1]);
	}
};

int n, A[N];

int I[N], DP[N], TO[N];

int bs(int s) {
	mono_deque<pii> D;
	D.push_back(make_pair(0, 0));
	int l = 0, r = 0;
	for(int i = 1; i <= n; ++i) {
		int x = A[I[i]], _l = i - s, _r = i - A[I[i]];

		if(_l > _r) return -1;

		for(l; l < _l; ++l) D.pop_front();
		
		if(r < _r) 
			for(r; r < _r; ++r) D.push_back(make_pair(DP[r + 1], r + 1));
		else 
			for(r; r > _r; --r) D.pop_back(); 

		pii res = D.max(); 
		DP[i] = res.X + 1;
		TO[i] = res.Y;
//		D.print();
//		printf("%d %d %d\n", i, DP[i], TO[i]);
	}
	return DP[n];
}

int main() {
	scanf("%d", &n); 
	for(int i = 1; i <= n; ++i) {
		scanf("%d", A + i); 
		I[i] = i;
	}
	sort(I + 1, I + n + 1, [](int a, int b) { return A[a] < A[b]; });

	int ans = bs(oo); 

	int lo = 1, hi = n;
	while(hi - lo > 1) {
		int mi = (lo + hi) / 2;
		int res = bs(mi);
		if(res < ans) lo = mi;
		else hi = mi;
	}

	ans = bs(hi);

	printf("%d\n", hi);
	printf("%d", ans);
	for(int i = n, j = n; i > 0; --i) {
		if(i == j) {
			printf("\n%d ", i - TO[i]);
			j = TO[i];
		}
		printf("%d ", I[i]); 
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

tea.cpp: In function 'int bs(int)':
tea.cpp:93:7: warning: statement has no effect [-Wunused-value]
   93 |   for(l; l < _l; ++l) D.pop_front();
      |       ^
tea.cpp:96:8: warning: statement has no effect [-Wunused-value]
   96 |    for(r; r < _r; ++r) D.push_back(make_pair(DP[r + 1], r + 1));
      |        ^
tea.cpp:98:8: warning: statement has no effect [-Wunused-value]
   98 |    for(r; r > _r; --r) D.pop_back();
      |        ^
tea.cpp:89:7: warning: unused variable 'x' [-Wunused-variable]
   89 |   int x = A[I[i]], _l = i - s, _r = i - A[I[i]];
      |       ^
tea.cpp: In instantiation of 'void mono_deque<T>::build() [with T = std::pair<int, int>]':
tea.cpp:53:23:   required from 'void mono_deque<T>::pop_front() [with T = std::pair<int, int>]'
tea.cpp:93:35:   required from here
tea.cpp:47:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = (D.size() - 1) / 2 + 1; i < D.size(); ++i) R.push(D[i]);
      |                                       ~~^~~~~~~~~~
tea.cpp: In function 'int main()':
tea.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
tea.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10