oj.uz

Submission #197293

# Submission time Handle Problem Language Result Execution time Memory
197293 2020-01-20T08:28:36 Z Redhood DEL13 (info1cup18_del13) C++14
40 / 100
 35 ms 888 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){

//    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;
}

Compilation message

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.0 / 15.0

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

Subtask #2
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is partially correct
2 Correct 5 ms 376 KB Output is partially correct
3 Correct 19 ms 504 KB Output is partially correct
4 Correct 20 ms 376 KB Output is partially correct

Subtask #3
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 504 KB Output is partially correct
2 Correct 9 ms 380 KB Output is partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is partially correct
2 Correct 5 ms 376 KB Output is partially correct
3 Correct 19 ms 504 KB Output is partially correct
4 Correct 20 ms 376 KB Output is partially correct
5 Correct 4 ms 252 KB Output is partially correct
6 Correct 4 ms 256 KB Output is partially correct
7 Correct 4 ms 256 KB Output is partially correct

Subtask #5
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is partially correct
2 Correct 5 ms 376 KB Output is partially correct
3 Correct 19 ms 504 KB Output is partially correct
4 Correct 20 ms 376 KB Output is partially correct
5 Correct 4 ms 252 KB Output is partially correct
6 Correct 4 ms 256 KB Output is partially correct
7 Correct 4 ms 256 KB Output is partially correct
8 Correct 28 ms 632 KB Output is partially correct
9 Correct 35 ms 760 KB Output is partially correct
10 Correct 31 ms 836 KB Output is partially correct
11 Correct 31 ms 888 KB Output is partially correct