Submission #862238

#	Time	Username	Problem	Language	Result	Execution time	Memory
862238		AbdelmagedNour	Volontiranje (COCI21_volontiranje)	C++17	110 / 110	224 ms	92456 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int a[n],lis[n]={};
	for(int i=0;i<n;i++)cin>>a[i];
	vector<int>dp;
	for(int i=0;i<n;i++){
		auto it=upper_bound(dp.begin(),dp.end(),a[i]);
		if(it==dp.end())dp.push_back(a[i]);
		else *it=a[i];
		lis[i]=upper_bound(dp.begin(),dp.end(),a[i])-dp.begin();
	}
	int mx=dp.size();
	vector<vector<int>>lvl(mx+1);
	for(int i=0;i<n;i++)lvl[lis[i]].push_back(i);
	for(int i=1;i<=mx;i++)reverse(lvl[i].begin(),lvl[i].end());
	vector<vector<int>>ans;
	vector<int>cur;
	while(!lvl[1].empty()||!cur.empty()){
		if(cur.empty())cur.push_back(lvl[1].back()),lvl[1].pop_back();
		else if(cur.size()==mx)ans.push_back(cur),cur.clear();
		else{
			int nxt=cur.size()+1;
			while(!lvl[nxt].empty()&&lvl[nxt].back()<cur.back())lvl[nxt].pop_back();
			if(!lvl[nxt].empty()&&a[lvl[nxt].back()]>a[cur.back()])cur.push_back(lvl[nxt].back()),lvl[nxt].pop_back();
			else cur.pop_back();
		}
	}
	cout<<ans.size()<<" "<<mx<<"\n";
	for(auto v:ans){
		for(auto x:v)cout<<x+1<<" ";
		cout<<"\n";
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:28:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   else if(cur.size()==mx)ans.push_back(cur),cur.clear();
      |           ~~~~~~~~~~^~~~

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