oj.uz

Submission #197299

# Submission time Handle Problem Language Result Execution time Memory
197299 2020-01-20T08:53:18 Z Redhood DEL13 (info1cup18_del13) C++14
100 / 100
 41 ms 1332 KB 
#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){
    if(len(nums)==1)return{};
//    for(auto i : nums)cout << i << ' ';
//    cout << endl << endl;
    vector < int > main;


    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){
            main.pb(nums[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);
    vector < int > pred(len(seg) + 1);
    dp[0] = 1;
    if(done[0])dp[1]=1 , pred[1] = 0;
    for(int i = 2; i <= len(seg);++i){
        if((done[i - 1]||seg[i-1]==0) && dp[i - 1]){
            dp[i] = 1;
            pred[i] = 0;
            continue;
        }
        if((seg[i-1]>=2)&&(seg[i-2]>=4)&&dp[i-1]){
            dp[i] = 1;
            pred[i] = 1;
        }
        if((seg[i-1]>=2)&&(seg[i-2]>=2)&&dp[i-2]){
            dp[i] = 1;
            pred[i] = 2;
        }
    }
    if(!dp[len(seg)])return {-1};

    int curr = len(seg);
    while(curr > 0){
//        cout << " CURR " << curr << '\n';
        if(pred[curr]==0){
            curr--;
            continue;
        }
        main.pb(nums[curr-1]);
        main.pb(nums[curr-1]);
        seg[curr-1]-=2;
        seg[curr-2]-=2;
        if(pred[curr]==1){
            curr--;
        }else {
            curr -= 2;
        }
    }
    vector < int > extra;
    for(int i = 0; i < len(nums) - 1; ++i){
//        assert(seg[i] >= 0);
        int pos = nums[i] + (nums[i+1]-nums[i]-1 + 1) / 2;
        while(seg[i] > 0){
            extra.pb(pos);
            seg[i] -= 2;
        }
    }
//    for(int i = 0 ; i < len(nums) - 1; ++i)
//            assert(seg[i]==0);
    vector < int > answer;
//    cout << " MAIN : \n";
//    for(auto u : main)cout << u << endl;
//    cout << endl;

    for(auto u : extra)answer.pb(u);
    for(auto u : main)answer.pb(u);
    return answer;
}
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){
//            if(len(answer) >= 0){
//                cout << 0 << '\n';
//                cout << '\n';
//            }
            cout << len(answer) << '\n';
            for(auto &i : answer)cout << i << ' ';
            cout << '\n';
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 252 KB Output is correct
2 Correct 5 ms 252 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 252 KB Output is correct
2 Correct 5 ms 252 KB Output is correct
3 Correct 21 ms 376 KB Output is correct
4 Correct 22 ms 440 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 508 KB Output is correct
2 Correct 8 ms 376 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 252 KB Output is correct
2 Correct 5 ms 252 KB Output is correct
3 Correct 21 ms 376 KB Output is correct
4 Correct 22 ms 440 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 252 KB Output is correct
2 Correct 5 ms 252 KB Output is correct
3 Correct 21 ms 376 KB Output is correct
4 Correct 22 ms 440 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 31 ms 504 KB Output is correct
9 Correct 35 ms 620 KB Output is correct
10 Correct 32 ms 536 KB Output is correct
11 Correct 41 ms 1332 KB Output is correct