Submission #623346

#TimeUsernameProblemLanguageResultExecution timeMemory
623346Theo830DEL13 (info1cup18_del13)C++17
0 / 100
9 ms2524 KiB
#include <bits/stdc++.h> using namespace std; typedef int ll; const ll INF = 1e9+7; const ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ii,ll> #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training ll dp[100005][3]; vll arr; ll siz; ll solve(ll idx,ll last){ if(idx == siz-1){ ll num = arr[idx] - last; if(num % 2 == 0){ if((arr[idx] % 2) == 0 && last == 0){ return false; } return true; } return false; } if(dp[idx][last] != -1){ return dp[idx][last]; } bool ok = 0; ll num = arr[idx] - last; if(num < 0){ return false; } if(num % 2 == 0){ if(num >= 2){ ok |= solve(idx + 1,2); } if(num == 0 || last >= 2){ ok |= solve(idx + 1,0); } } else{ ok = solve(idx + 1,1); } return dp[idx][last] = ok; } int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); ll t; cin>>t; while(t--){ ll n,r; cin>>n>>r; ll last = 0; arr.clear(); f(i,0,r){ ll a; cin>>a; arr.pb(a - last - 1); last = a; } arr.pb(n - last); siz = arr.size(); f(i,0,siz+5){ f(j,0,3){ dp[i][j] = -1; } } f(i,0,siz){ if(arr[i] > 4){ if(arr[i] % 2 == 0){ arr[i] = 4; } else{ arr[i] = 3; } } //cout<<arr[i]<<" "; } //cout<<"\n"; bool ok = solve(0,0); if(!ok){ cout<<"-1\n"; } else{ cout<<"0\n"; } } }
#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...