| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 493943 |
2021-12-13T12:50:57 Z |
balbit |
DEL13 (info1cup18_del13) |
C++14 |
|
11 ms |
1428 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<ll, ll>
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int maxn = 2e5+5;
bool dp[maxn][3]; // none, even, odd
//int type[maxn][3];
int who[maxn];
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
int T; cin>>T;
while (T--) {
int N, m; cin>>N>>m;
vector<int> a;
a.pb(0);
REP(i,m) {
int x; cin>>x; a.pb(x);
}
a.pb(N+1);
sort(ALL(a));
dp[0][0] = 1;
for (int i = 1; i<SZ(a); ++i) {
memset(dp[i], 0, sizeof dp[i]);
int df = a[i] - a[i-1] - 1;
if (df == 0) {
dp[i][0] = dp[i-1][0];
}else{
if (df % 2 == 0) {
dp[i][0] = dp[i-1][1]; // if even, can del everything
dp[i][2] = dp[i-1][2]; // if odd, leaves me with odd
dp[i][1] = (df >= 4 && dp[i-1][1]) || dp[i-1][0]; // if even and leaves me space, ok
}else{
dp[i][0] = dp[i-1][2];
dp[i][2] = (df >= 3 && dp[i-1][1]) || dp[i-1][0]; // i want odd number left
dp[i][1] = (df >= 2 && dp[i-1][2]); // i want even left, so i want to remove odd number
}
}
bug(i, df, dp[i][0], dp[i][1], dp[i][2]);
}
if (dp[SZ(a)-1][0]) {
int tp = 0;
for (int i = SZ(a)-1; i>0; --i) {
int df = a[i] - a[i-1] - 1;
who[i] = tp;
bug(i, tp);
if (df == 0) {
continue;
}
if (df % 2 == 0) {
if (tp == 0) tp = 1;
else if (tp == 1) {
if (dp[i-1][0]) tp=0;
else tp = 1;
}
}else{
bug(i, tp, "hmm");
if (tp == 0) tp = 2;
else if (tp == 1) tp = 2;
else if (tp == 2) {
if (dp[i-1][0]) tp = 0;
else tp = 1;
}
}
}
vector<int> re;
int took = 0;
for (int i = 1; i<SZ(a); ++i) {
int p = a[i];
int df = a[i] - a[i-1] - 1;
int need = df;
if (who[i] == 1) need -= 2; if (who[i] == 2) need -= 1;
if (who[i-1] == 1) need -= 2; if (who[i-1] == 2) need -= 1;
bug(need);
assert(need >= 0 && (need%2==0));
int md = (a[i] + a[i-1]) / 2;
REP(pp, need/2) re.pb(md);
}
for (int i = 1; i<SZ(a)-1; ++i) {
if (who[i] == 1) {
re.pb(a[i]);
re.pb(a[i]);
}
if (who[i] == 2) {
re.pb(a[i]);
}
}
cout<<SZ(re)<<endl;
for (int t : re) cout<<t<<' ';
cout<<endl;
}else{
cout<<-1<<endl;
}
}
}
Compilation message
del13.cpp: In function 'int main()':
del13.cpp:94:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
94 | if (who[i] == 1) need -= 2; if (who[i] == 2) need -= 1;
| ^~
del13.cpp:94:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
94 | if (who[i] == 1) need -= 2; if (who[i] == 2) need -= 1;
| ^~
del13.cpp:95:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
95 | if (who[i-1] == 1) need -= 2; if (who[i-1] == 2) need -= 1;
| ^~
del13.cpp:95:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
95 | if (who[i-1] == 1) need -= 2; if (who[i-1] == 2) need -= 1;
| ^~
del13.cpp:91:21: warning: unused variable 'p' [-Wunused-variable]
91 | int p = a[i];
| ^
del13.cpp:89:17: warning: unused variable 'took' [-Wunused-variable]
89 | int took = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
4 ms |
332 KB |
Output is correct |
| 4 |
Correct |
5 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
4 ms |
332 KB |
Output is correct |
| 4 |
Correct |
5 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
4 ms |
332 KB |
Output is correct |
| 4 |
Correct |
5 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
7 ms |
480 KB |
Output is correct |
| 9 |
Correct |
10 ms |
716 KB |
Output is correct |
| 10 |
Correct |
7 ms |
764 KB |
Output is correct |
| 11 |
Correct |
11 ms |
1428 KB |
Output is correct |
