Submission #408886

#	Time	Username	Problem	Language	Result	Execution time	Memory
408886		Atill83	DEL13 (info1cup18_del13)	C++14	12 / 100	57 ms	11072 KiB

del13

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void solve(){
    int n, q;
    cin>>n>>q;
    vector<int> islem;
    vector<set<int>> once = {{}};
    vector<int> a = {0};
    cerr<<"garip kont 1"<<endl;
    for(int i = 0; i < q; i++){
        int x;
        cin>>x;
        once.push_back(set<int>());
        for(int j = a.back() + 1; j < x; j++){
            once.back().insert(j);
        }

        while(once.back().size() > 3){
            auto u = once.back().begin();
            u = once.back().erase(u);
            islem.push_back((*u));
            u = next(u);
            u = once.back().erase(u);
        }

        a.push_back(x);
    }
    once.push_back(set<int>());
    
    for(int j = a.back() + 1; j <= n; j++)
        once.back().insert(j);
    while(once.back().size() > 3){
        auto u = once.back().begin();
        u = once.back().erase(u);
        islem.push_back((*u));
        u = next(u);
        u = once.back().erase(u);
    }
    if(q < 1 && n != 1){
        cout<<-1<<endl;
        return;
    }
    cerr<<"garip kont 2"<<endl;

    vector<vector<bool>> dp(q + 2, vector<bool>(4, 0));
    vector<vector<pii>> prev(q + 2, vector<pii>(4));
    cerr<<q + 1<<" "<<once.size()<<endl;
    dp[0][once[1].size()] = 1;
    if(once[1].size() == 3)
        dp[0][1] = 1;
    for(int i = 1; i <= q; i++){
        for(int l = 0; l <= once[i + 1].size(); l++){
            int is = (int) once[i + 1].size() - l;
            dp[i][l] = dp[i - 1][is];
            prev[i][l] = {is, 0};
            if(once[i + 1].size() == 3){
                int is2 = (int) once[i + 1].size() - l - 2;
                if(is2 >= 0 && dp[i - 1][is2]){
                    dp[i][l] = dp[i - 1][is2];
                    prev[i][l] = {is2, 1};
                }
            }
        }
    }


    cerr<<"garip kont 3"<<endl;
    if(dp[q][0]){
        int l = 0;
        /*for(int j = q; j >= 1; j--){ // l j'nin kac biraktigi, cur.ff kac tane yaptigi ayni zamanda oncekinin kac biraktigi
            pii cur = prev[j][l];
            if(cur.ss == 0){
                for(int i = 0; i < cur.ff; i++){
                    islem.push_back(j);
                }
                l = once[j].size() - cur.ff;
            }
        }*/

        cout<<islem.size()<<endl;
        for(int i: islem)
            cout<<i<<" ";
        cout<<endl;
    }else{
        cout<<-1<<endl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    int t;
    cin>>t;

    while(t--)
        solve();



    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

del13.cpp: In function 'void solve()':
del13.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int l = 0; l <= once[i + 1].size(); l++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~
del13.cpp:81:13: warning: unused variable 'l' [-Wunused-variable]
   81 |         int l = 0;
      |             ^

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