제출 #1202221

#제출 시각아이디문제언어결과실행 시간메모리
1202221MighilonVolontiranje (COCI21_volontiranje)C++20
0 / 110
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "../Library/debug.h" #else #define dbg(x...) #endif typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) for (int i = 0; i < (a); ++i) #define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i) #define trav(a, x) for (auto& a : x) #define f first #define s second #define pb push_back #define sz(x) (int)(x).size() #define all(x) x.begin(), x.end() const char nl = '\n'; const int INF = 1e9; const int MOD = 1e9 + 7; void solve(){ int n; cin>>n; vi a(n); F0R(i,n)cin>>a[i]; set<pi> st; vi _dp; // LIS at index i F0R(i,n){ int pos=upper_bound(_dp.begin(),_dp.end(),a[i]) - _dp.begin(); if(pos==sz(_dp)) _dp.pb(a[i]); else _dp[pos]=a[i]; st.insert({pos+1,i}); } int m=sz(_dp); vector<vi> ans; while(1){ vi tmp; pi last={n,n}; for(int i=m;i>0;--i){ set<pi>::iterator it; while(1){ it=lower_bound(all(st),pi{i,-1}); if(it==st.end()||it->f!=i||it->s>last.s) break; if(a[it->s]>last.f){ st.erase(it); } else{ break; } } if(it==st.end()||it->f!=i||it->s>last.s){ break; } last={a[it->s],it->s}; tmp.pb(it->s); st.erase(it); } if(sz(tmp)!=m){ break; } ans.pb(tmp); } cout<<sz(ans)<<" "<<m<<nl; trav(i,ans){ reverse(all(i)); trav(j,i)cout<<j+1<<" "; cout<<nl; } } int32_t main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int TC = 1; // cin >> TC; while(TC--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...