제출 #197391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197391		kmekhovich	DEL13 (info1cup18_del13)	C++14	15 / 100	34 ms	4868 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;
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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 0 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30