oj.uz

Submission #408886

# Submission time Handle Problem Language Result Execution time Memory
408886 2021-05-19T18:58:45 Z Atill83 DEL13 (info1cup18_del13) C++14
12 / 100
 57 ms 11072 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 332 KB Output is partially correct
2 Correct 12 ms 316 KB Output is partially correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 332 KB Output is partially correct
2 Correct 12 ms 316 KB Output is partially correct
3 Incorrect 54 ms 456 KB Output isn't correct
4 Incorrect 57 ms 432 KB Output isn't correct

Subtask #3
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 780 KB Output is partially correct
2 Correct 49 ms 2468 KB Output is partially correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 332 KB Output is partially correct
2 Correct 12 ms 316 KB Output is partially correct
3 Incorrect 54 ms 456 KB Output isn't correct
4 Incorrect 57 ms 432 KB Output isn't correct
5 Incorrect 4 ms 332 KB Output isn't correct
6 Incorrect 4 ms 332 KB Output isn't correct
7 Incorrect 4 ms 332 KB Output isn't correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 332 KB Output is partially correct
2 Correct 12 ms 316 KB Output is partially correct
3 Incorrect 54 ms 456 KB Output isn't correct
4 Incorrect 57 ms 432 KB Output isn't correct
5 Incorrect 4 ms 332 KB Output isn't correct
6 Incorrect 4 ms 332 KB Output isn't correct
7 Incorrect 4 ms 332 KB Output isn't correct
8 Incorrect 46 ms 2936 KB Output isn't correct
9 Incorrect 43 ms 4632 KB Output isn't correct
10 Incorrect 41 ms 5504 KB Output isn't correct
11 Incorrect 52 ms 11072 KB Output isn't correct