제출 #1167667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167667		emptypringlescan	Volontiranje (COCI21_volontiranje)	C++20	110 / 110	259 ms	148200 KiB

Main

#include <bits/stdc++.h>
using namespace std;
vector<pair<pair<int,int>,pair<int,int> > > ppl[1000005];
vector<int> anc;
int v[1000005],cnt[1000005];
int dfs(int x, int y){
	if(v[ppl[x][y].first.second]) return 0;
	v[ppl[x][y].first.second]=1;
	cnt[x]=max(cnt[x],y+1);
	anc.push_back(ppl[x][y].first.second);
	if(x==0) return 1;
	for(int i=max(cnt[x-1],ppl[x][y].second.first); i<=ppl[x][y].second.second; i++){
		if(dfs(x-1,i)) return 1;
	}
	anc.pop_back();
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
    int n;
    cin >> n;
    int arr[n];
    int big=0;
    for(int i=0; i<n; i++){
		cin >> arr[i];
		int lo=0,hi=n,mid;
		while(lo<hi){
			mid=(lo+hi)/2;
			if(ppl[mid].empty()||ppl[mid].back().first.first>=arr[i]) hi=mid;
			else lo=mid+1;
		}
		int x=lo;
		big=max(big,x);
		if(x==0){
			ppl[x].push_back({{arr[i],i},{-1,-1}});
		}
		else{
			lo=0,hi=(int)ppl[x-1].size()-1;
			while(lo<hi){
				mid=(lo+hi)/2;
				if(ppl[x-1][mid].first.first>=arr[i]) lo=mid+1;
				else hi=mid;
			}
			ppl[x].push_back({{arr[i],i},{lo,ppl[x-1].size()-1}});
			//cout << i << ' ' << x << ' ' << lo << ' ' << ppl[x-1].size()-1 << '\n';
		}
	}
	vector<vector<int> > ans;
	for(int i=0; i<(int)ppl[big].size(); i++){
		anc.clear();
		if(dfs(big,i)){
			reverse(anc.begin(),anc.end());
			ans.push_back(anc);
		}
	}
	cout << (int)ans.size() << ' ' << big+1 << '\n';
	for(auto i:ans){
		for(int j:i) cout << j+1 << ' ';
		cout << '\n';
	}
}

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