Submission #493943

#	Time	Username	Problem	Language	Result	Execution time	Memory
493943		balbit	DEL13 (info1cup18_del13)	C++14	100 / 100	11 ms	1428 KiB

del13

#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 (stderr)

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;
      |                 ^~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25
• Subtask 5: 30 / 30