Submission #866714

#	Time	Username	Problem	Language	Result	Execution time	Memory
866714		Cyber_Wolf	Volontiranje (COCI21_volontiranje)	C++17	110 / 110	212 ms	155056 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
 
using namespace std;
using namespace __gnu_pbds;
 
#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mid (lr+hr)/2
 
const lg N = 1e6+5;
 
vector<lg> val(N), lev[N], v(N), cur;
vector<vector<lg>> ans;
lg lis = 0, n;

bool dfs(lg idx)
{
	// cout << "IDX: " << idx << '\n';
	// for(auto it : cur)	cout << it << ' ';
	// cout << '\n';
	if(idx == lis)
	{
		ans.push_back(cur);
		return true;
	}
	while(lev[idx].size() && lev[idx].back() < cur.back())	lev[idx].pop_back();
	while(lev[idx].size())
	{
		if(v[lev[idx].back()] < v[cur.back()])
		{
			return false;
		}
		cur.push_back(lev[idx].back());
		lev[idx].pop_back();
		if(dfs(idx+1))	return true;
		cur.pop_back();
	}
	return false;
}
 
int main()
{
	fastio;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> v[i];
		if(!lis || val[lis-1] < v[i])
		{
			val[lis] = v[i];
			lev[lis].push_back(i);
			lis++;
		}
		else{
			lg idx = lower_bound(val.begin(), val.begin()+lis, v[i])-val.begin();
			lev[idx].push_back(i);
			val[idx] = v[i];
		}
	}	
	for(int i = 0; i <= n; i++)	reverse(lev[i].begin(), lev[i].end());
	while(lev[0].size())
	{
		cur.push_back(lev[0].back());
		lev[0].pop_back();
		dfs(1);
		cur.clear();
	}
	cout << ans.size() << ' ' << lis << '\n';
	for(auto it : ans)
	{
		for(auto it2 : it)	cout << it2 << ' ';
		cout << '\n';
	}
 
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60