oj.uz

Submission #197391

# Submission time Handle Problem Language Result Execution time Memory
197391 2020-01-20T18:13:21 Z kmekhovich DEL13 (info1cup18_del13) C++14
15 / 100
 34 ms 4868 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#define pb push_back
#define fst first
#define snd second
#define all(c) (c).begin(), (c).end()
typedef long long ll;
typedef long double ld;
const ll INF64 = 1e18 + 228;
const int INF32 = 1e9 + 1337;
const int MOD = 1e9 + 7;
const ld eps = 1e-7;
const int N = 1e3 + 3;
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t--)
    {
        ll n, q;
        cin >> n >> q;
        vector<ll> a(q);
        set<ll> aa;
        vector<ll> pref(n, 0);
        for(auto& it : a)
        {
            cin >> it;
            it--;
            aa.insert(it);
        }
        for(int i = 0; i < n; i++)
        {
            pref[i] = aa.count(i);
            if(i) pref[i] += pref[i - 1];
        }
        int lst = -1;
        vector< pair<ll, ll> > x;
        for(auto& it : a)
        {
            if(lst + 1 == it)
            {
                lst = it;
                continue;
            }
            x.pb({it - lst - 1, lst + 1});
            lst = it;
        }
        if(lst != n - 1)
            x.pb({n - 1 - lst, lst + 1});
        vector<ll> ans;
        for(auto& it : x)
        {
            if(it.fst > 2)
            {
                ll cnt = (it.fst - 1) / 2;
                for(int i = 0; i < cnt; i++)
                    ans.pb(it.snd + it.fst / 2);
                if(it.fst & 1)
                    it.fst = 1;
                else
                    it.fst = 2;
            }
        }
        bool bad = 0;
        int z = 0;
        for(int i = 1; i < x.size(); i++)
        {
            if(z == i) continue;
            if(x[z].fst == 0)
            {
                z++;
                continue;
            }
            if(x[i].fst == 0) continue;
            if(pref[x[i].snd] - pref[x[z].snd] > 1)
            {
                bad = 1;
                break;
            }
            ll mn = min(x[z].fst, x[i].fst);
            x[z].fst -= mn;
            x[i].fst -= mn;
            for(int j = 0; j < mn; j++)
            {
                ans.pb(x[i].snd - 1);
            }
            if(x[z].fst > mn)
            {
                continue;
            }
            z++;
        }
        for(int i = 0; i < x.size(); i++)
            bad |= x[i].fst;
        if(bad)
            cout << "-1\n";
        else
        {
            cout << ans.size() << "\n";
            for(auto& it : ans)
                cout << it + 1 << " ";
            cout << "\n";
        }
    }

    return 0;
}

Compilation message

del13.cpp: In function 'int main()':
del13.cpp:72:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < x.size(); i++)
                        ~~^~~~~~~~~~
del13.cpp:99:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < x.size(); i++)
                        ~~^~~~~~~~~~

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Incorrect 3 ms 376 KB Output isn't correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Incorrect 9 ms 504 KB Output isn't correct
4 Incorrect 9 ms 504 KB Output isn't correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 632 KB Output is correct
2 Correct 10 ms 2092 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Incorrect 9 ms 504 KB Output isn't correct
4 Incorrect 9 ms 504 KB Output isn't correct
5 Incorrect 3 ms 376 KB Output isn't correct
6 Incorrect 3 ms 376 KB Output isn't correct
7 Incorrect 3 ms 376 KB Output isn't correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Incorrect 9 ms 504 KB Output isn't correct
4 Incorrect 9 ms 504 KB Output isn't correct
5 Incorrect 3 ms 376 KB Output isn't correct
6 Incorrect 3 ms 376 KB Output isn't correct
7 Incorrect 3 ms 376 KB Output isn't correct
8 Incorrect 20 ms 1800 KB Output isn't correct
9 Incorrect 27 ms 2112 KB Output isn't correct
10 Incorrect 27 ms 2492 KB Output isn't correct
11 Incorrect 34 ms 4868 KB Output isn't correct