Submission #197569

#	Time	Username	Problem	Language	Result	Execution time	Memory
197569		kmekhovich	DEL13 (info1cup18_del13)	C++14	0 / 100	33 ms	4864 KiB

del13

#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;
bool check(ll &n, vector<ll> &a, vector<ll> &ans)
{
    set<ll> b;
    for(int i = 0; i < n; i++)
        b.insert(i);
    for(auto& it : ans)
    {
        if(b.find(it) != b.end())
        {
            b.erase(prev(b.find(it)));
            b.erase(next(b.find(it)));
        }
        else
        {
            return 0;
        }
    }
    for(auto& it : a)
    {
        if(b.find(it) != b.end())
        {
            continue;
        }
        else
        {
            return 0;
        }
    }
    return (a.size() == b.size());
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    mt19937 rng(46);
//    uniform_int_distribution<int> rnd;
    int t;
    cin >> t;
    while(t--)
    {
        ll n, q;
        cin >> n >> q;
//        n = 10; q = 4;
        vector<ll> a(q);
        set<ll> aa;
        vector<ll> pref(n, 0);
//        int mask = 0;
//        while(__builtin_popcount(mask) != q)
//        {
//            mask = rnd(rng) % (1 << n);
//        }
//        int itt = 0;
//        for(int i = 0; i < n; i++)
//        {
//            if((mask >> i) & 1)
//            {
//                a[itt++] = i;
//                aa.insert(i);
//            }
//        }
        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;
        vector<ll> fans;
        for(auto& it : x)
        {
            if(it.fst > 4)
            {
                ll cnt = (it.fst - 3) / 2;
                for(int i = 0; i < cnt; i++)
                    fans.pb(it.snd + it.fst / 2);
                if(it.fst & 1)
                    it.fst = 3;
                else
                    it.fst = 4;
            }
        }
        bool bad = 0;
        int lastsize = x.back().fst;
        for(int i = 1; i < x.size(); i++)
        {
            if(x[i].fst == 0) continue;
            if(pref[x[i].snd] - pref[x[i - 1].snd] > 1)
            {
                bad = 1;
                break;
            }
            ll mn = min(x[i - 1].fst, x[i].fst);
            if(x[i - 1].fst - mn)
            {
                fans.pb(x[i - 1].snd + x[i - 1].fst / 2);
                x[i - 1].fst -= 2;
            }
            mn = min(x[i - 1].fst, x[i].fst);
            x[i - 1].fst -= mn;
            x[i].fst -= mn;
            for(int j = 0; j < mn; j++)
            {
                ans.pb(x[i].snd - 1);
            }
        }
        if(x.back().fst > 1 && lastsize > 2)
        {
            fans.pb(x.back().snd + x.back().fst / 2);
            x.back().fst -= 2;
        }
        for(int i = 0; i < x.size(); i++)
            bad |= x[i].fst;
        if(bad)
        {
            cout << "-1\n";
        }
        else
        {
            cout << ans.size() + fans.size() << "\n";
            for(auto& it : fans)
                cout << it + 1 << " ";
            for(auto& it : ans)
                cout << it + 1 << " ";
            cout << "\n";
//            bool verdict = check(n, a, ans);
//            if(!verdict)
//            {
//                cout << "WA\n";
//                return 0;
//            }
//            else
//                cout << "OK\n";
        }
    }

    return 0;
}

Compilation message (stderr)

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

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