Submission #210984

#TimeUsernameProblemLanguageResultExecution timeMemory
210984ryanseeDEL13 (info1cup18_del13)C++14
40 / 100
37 ms1556 KiB
#include "bits/stdc++.h" using namespace std; #define FAST ios_base::sync_with_stdio(false); cin.tie(0); #define pb push_back #define eb emplace_back #define ins insert #define ph push #define f first #define s second #define cbr cerr << "hi\n" #define mmst(x, v) memset((x), v, sizeof ((x))) #define siz(x) ll(x.size()) #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng) inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); } typedef long long ll; typedef long double ld; #define FOR(i,s,e) for(ll i=s;i<=ll(e);++i) #define DEC(i,s,e) for(ll i=s;i>=ll(e);--i) typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi; #define LLINF ((long long)1e18) #define INF int(1e9+1e6) #define MAXN (300006) bool state[MAXN]; void solve(){ mmst(state,0); ll n,q;cin>>n>>q; FOR(i,0,q-1){ ll a; cin>>a; state[a]=1; } vector<ll> comp; vector<vector<bool>> dp(2,vector<bool>(n+4,0)); vector<ll> moves, ans, re; auto gogo=[&](){ if(comp.empty())return 1; vector<vector<ll>> came(siz(comp), vector<ll>()); FOR(i,0,siz(comp)-1){ came[i].resize(comp[i]+3); FOR(j,0,comp[i]+2) dp[i&1][j]=0, came[i][j]=-1; if(i) for(ll j=1;j<=min(comp[i-1],comp[i]);++j) if(dp[(i-1)&1][j]) { dp[i&1][comp[i]-j]=1, came[i][comp[i]-j]=j; } if(comp[i]>2){ DEC(j,comp[i]-1,0){ if(dp[i&1][j+2]&&!dp[i&1][j]){ came[i][j]=came[i][j+2]; } dp[i&1][j]=dp[i&1][j]|dp[i&1][j+2]; } } if(i==0||dp[(i-1)&1][0]){ dp[i&1][comp[i]]=1, came[i][comp[i]]=0; DEC(j,comp[i]-1,1){ if(dp[i&1][j+2]&&!dp[i&1][j]){ came[i][j]=came[i][j+2]; } dp[i&1][j]=dp[i&1][j]|dp[i&1][j+2]; } } } if(dp[(siz(comp)-1)&1][0]){ ll x=siz(comp)-1, y=0; assert(moves.empty()); moves.pb(0); while(x){ assert(~came[x][y]), moves.pb(came[x][y]), y=came[x][y], -- x; } reverse(all(moves)); assert(moves.size()==comp.size()); re.clear(), re.resize(moves.size(),0); FOR(i,0,siz(moves)-1){ if(i==0) { re[i]=moves[i], moves[i]=comp[i]-moves[i]; }else{ re[i]=moves[i], moves[i]=comp[i]-re[i-1]-moves[i]; } } return 1; } cout<<"-1\n"; return 0; }; ll past=0; auto get_move=[&](){ assert(moves.size()==comp.size()); ll opast=past; FOR(i,0,siz(comp)-1){ ll to_bye=moves[i]; assert(to_bye%2==0); to_bye/=2; assert(comp[i]-to_bye*2>=1); while(to_bye--){ ans.pb(past+2); } past += comp[i] + 1; } past=opast; FOR(i,0,siz(comp)-1){ past+=comp[i]+1; moves[i]=re[i]; if(siz(comp)-1==i)assert(moves[i]==0); while(moves[i]--)ans.pb(past); } }; FOR(i,1,n){ if(state[i]==0){ if(i>1&&state[i-1]==0) { ++ comp.back(); }else{ comp.pb(1); } }else{ if(i>1&&state[i-1]==1){ if(!gogo())return; get_move(); comp.clear(); moves.clear(), re.clear(); ++ past; }else { past+=(i==1); assert(i==1||comp.size()); } } } if(!gogo())return; get_move(); if(state[n]==0)assert(past==n+1); else assert(past==n); cout<<ans.size()<<'\n'; for(auto i:ans)assert(i>1&&i<n),cout<<i<<' ';cout<<'\n'; } int main(){ FAST ll t; cin>>t; while(t--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...