Submission #65163

#	Time	Username	Problem	Language	Result	Execution time	Memory
65163		reality	JOIRIS (JOI16_joiris)	C++17	45 / 100	1085 ms	2880 KiB

joiris

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
vector < vi > A;
int MX,n,k;
vi One;
vector < pii > answer;
void G(int sz) {
    while (A.size() <= sz)
        A.pb(vi(n,0));
}
int add1(int index) {
    int ok = 0;
    answer.pb(mp(1,index));
    int lst = -1;
    for (int i = 0;i < A.size();++i)
        if (A[i][index] == 1)
            lst = i;
    for (int cs = 0,i = lst + 1;cs < k && i <= lst + k;++cs,++i) {
        G(i);
        A[i][index] = 1;
        if (A[i] == One) {
            A.erase(A.begin() + i);
            ok = 1;
            --i;--lst;
        }
    }
    return ok;
}
int add2(int index) {
    int ok = 0;
    answer.pb(mp(2,index));
    int lst = -1;
    for (int i = index;i < index + k;++i)
        for (int j = 0;j < A.size() && A[j][i] == 1;++j)
            smax(lst,j);
    G(++lst);
    for (int i = index;i < index + k;++i)
        A[lst][i] = 1;
    if (A[lst] == One)
        A.erase(A.begin() + lst),ok = 1;
    return ok;
}
int main(void) {
    cin>>n>>k;
    for (int i = 0;i < n;++i)
        One.pb(1);
    vi s(n);
    for (auto & it : s)
        cin>>it;
    vi sum(k,0);
    for (int i = 0;i < n;++i)
        (sum[i % k] += s[i]) %= k;
    int ok = 0;
    for (int i = 0;i + 1 < (n % k);++i)
        if (sum[i] != sum[i + 1])
            return puts("-1") * 0;
    for (int i = (n % k);i + 1 < k;++i)
        if (sum[i] != sum[i + 1])
            return puts("-1") * 0;
    for (int i = 0;i < n;++i) {
        G(s[i]);
        for (int j = 0;j < s[i];++j)
            A[j][i] = 1;
    }
    for (int i = 1;i < n;++i) {
        while (s[i - 1] > s[i]) {
            add1(i);
            s[i] += k;
        }
    }
    for (int i = 0;i < A.size();++i) {
        int w = -1;
        while (w + 1 < n && A[i][w + 1] == 0)
            ++w;
        while (w >= k - 1) {
            if (add2(w - k + 1))
                --i;
            w -= k;
        }
    }
    for (int i = 0;i < k - 1;++i) {
        while (!A.empty() && !A.back()[i])
            add1(i);
    }
    if (!A.empty())
    for (int i = 0;i < (n % k);++i)
        while (!A.back()[i])
            add1(i);
    while (!A.empty()) {
        for (int i = (n % k);i < n;i += k)
            add2(i);
    }
    cout << (answer.size()) << '\n';
    for (auto it : answer)
        cout << it.fi << ' ' << (it.se + 1) << '\n';
    return 0;
}

Compilation message (stderr)

joiris.cpp: In function 'void G(int)':
joiris.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (A.size() <= sz)
            ~~~~~~~~~^~~~~
joiris.cpp: In function 'int add1(int)':
joiris.cpp:29:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i < A.size();++i)
                    ~~^~~~~~~~~~
joiris.cpp: In function 'int add2(int)':
joiris.cpp:48:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0;j < A.size() && A[j][i] == 1;++j)
                        ~~^~~~~~~~~~
joiris.cpp: In function 'int main()':
joiris.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i < A.size();++i) {
                    ~~^~~~~~~~~~
joiris.cpp:67:9: warning: unused variable 'ok' [-Wunused-variable]
     int ok = 0;
         ^~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 55