제출 #197293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197293		Redhood	DEL13 (info1cup18_del13)	C++14	40 / 100	35 ms	888 KiB

del13

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define len(x) (int)(x).size()


typedef long long ll;
typedef long double ld;

using namespace std;

vector<int> solve(vector<int>nums){

//    for(auto i : nums)cout << i << ' ';
//    cout << endl << endl;

    vector<int>seg;
    for(int i = 1; i < len(nums);++i){
        seg.pb(nums[i]-nums[i-1]-1);
    }
    bool sum = 0;
    for(auto u : seg)sum ^= (u&1);
    if(sum)return {-1};
    /// firstly close all 1

    vector < bool > done(len(seg));
    for(int i = 0 ; i < len(seg) - 1;++i){
        if(seg[i]&1){
            done[i] = 1;
            done[i + 1] = 1;
            seg[i]--;
            seg[i + 1]--;
        }
    }

//    cout << " SEGS \n";
//    for(auto i : seg)cout << i << ' ';
//    cout << "\n DONE\n";
//    for(int i = 0 ;  i <  len(seg);++i)cout << done[i];
//
//    cout << endl << endl;

    vector < bool > dp(len(seg) + 1);
    dp[0] = 1;
    if(done[0])dp[1]=1;
    for(int i = 2; i <= len(seg);++i){
        dp[i] = (dp[i - 2]&&(seg[i-1]>=2&&seg[i-2]>=2))|(dp[i - 1]&&(seg[i-2]>=4&&seg[i-1]>=2));
        if(done[i - 1]){
            dp[i] = (dp[i]|dp[i - 1]);
        }
        if(seg[i - 1] == 0)
            dp[i] = (dp[i]|dp[i - 1]);
    }
    if(!dp[len(seg)])return {-1};
    /// ask can or not
    return {};
}
signed main(){
    int t;
    cin >> t;
    while(t--){
        int n , q;
        cin >> n >> q;
        vector < int > pos(q);
        for(auto &i : pos)cin >> i;
        pos.insert(pos.begin() , 0);
        pos.pb(n+1);
        int sum = 0;
        vector < int > nums;
        int prev = 0;
        vector<int>answer;
        nums.pb(0);
        for(int i = 1; i < len(pos); ++i){
            if(pos[i-1]+1==pos[i]){
                vector<int>ans=solve(nums);
//                cout << endl;
//                for(auto &u : nums)cout << u << ' ' ;
//                cout <<  " ANS " << len(ans) << endl;
                for(auto u : ans)answer.pb(u);
                nums.clear();
            }
            nums.pb(pos[i]);
        }
        if(len(nums)>1){
            vector<int>ans=solve(nums);
            for(auto u : ans)answer.pb(u);
        }
        bool cant = 0;
        for(auto &i : answer){
            if(i == -1){
                cout<<-1<<'\n';
                cant = 1;
                break;
            }
        }

        if(!cant){
            cout << len(answer) << '\n';
            for(auto &i : answer)cout << i << ' ';
            cout << '\n';
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

del13.cpp: In function 'int main()':
del13.cpp:70:13: warning: unused variable 'sum' [-Wunused-variable]
         int sum = 0;
             ^~~
del13.cpp:72:13: warning: unused variable 'prev' [-Wunused-variable]
         int prev = 0;
             ^~~~

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