Submission #951475

#	Time	Username	Problem	Language	Result	Execution time	Memory
951475		Nhoksocqt1	Painting Walls (APIO20_paint)	C++17	40 / 100	82 ms	144588 KiB

paint

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;
const int MAXM = 50004;

vector<int> B[MAXM], C[MAXN];
int f[20004][2003];
int colNeed[MAXN], dp[MAXN], sum[MAXN], nArr, mArr, numCol;
bool dx[2003][20004], ok[MAXN];

int sub1(void) {
    for (int i = 1; i <= nArr; ++i) {
        if(sz(C[colNeed[i]]) == 0)
            return -1;

        dp[i] = C[colNeed[i]][0];
        sum[i] = sum[i - 1] + (i > 1 && (dp[i - 1] + 1) % mArr == dp[i]);
    }

    int res(0), maxi(1), lastok(-mArr);
    for (int i = 1; i <= nArr; ++i) {
        if(sum[i + mArr - 1] - sum[i] == mArr - 1 && (dp[i + mArr - 1] + 1) % mArr == dp[i])
            lastok = i;

        if(i == maxi) {
            if(lastok + mArr <= i)
                return -1;

            maxi = lastok + mArr;
            ++res;
        }
    }

    return res;
}

int sub3(void) {
    for (int j = 0; j < mArr; ++j) {
        for (int it = 0; it < sz(B[j]); ++it)
            dx[j][B[j][it]] = 1;
    }

    for (int i = 1; i + mArr - 1 <= nArr; ++i) {
        ok[i] = 0;
        for (int j = 0; j < mArr; ++j) {
            ok[i] = 1;
            for (int k = 0; k < mArr; ++k)
                ok[i] &= (dx[(j + k) % mArr][colNeed[i + k]]);

            if(ok[i])
                break;
        }
    }

    dp[0] = 0;
    for (int i = 1; i <= nArr; ++i)
        dp[i] = 1e9+7;

    for (int i = 0; i < nArr; ++i) {
        for (int j = 0; i + 1 - j > 0 && j < mArr; ++j) {
            if(ok[i + 1 - j])
                dp[i + mArr - j] = min(dp[i + mArr - j], dp[i] + 1);
        }
    }

    return (dp[nArr] >= 1e9) ? -1 : dp[nArr];
}

int sub4(void) {
    for (int j = 0; j < mArr; ++j) {
        for (int it = 0; it < sz(B[j]); ++it)
            dx[j][B[j][it]] = 1;
    }

    for (int i = nArr; i > 0; --i) {
        for (int j = mArr; j > 0; --j)
            f[i][j] = f[i + 1][j + 1] + (dx[j - 1][colNeed[i]]);
    }

    for (int i = 1; i + mArr - 1 <= nArr; ++i) {
        int lok(ok[i]);
        for (int j = 0; j < mArr; ++j) {
            ok[i] = (f[i][j + 1] + f[i + mArr - j][1] - f[i + mArr][j + 1] == mArr);
            if(ok[i])
                break;
        }

        if(lok != ok[i])
            exit(1);
    }

    dp[0] = 0;
    for (int i = 1; i <= nArr; ++i)
        dp[i] = 1e9+7;

    for (int i = 0; i < nArr; ++i) {
        for (int j = 0; i + 1 - j > 0 && j < mArr; ++j) {
            if(ok[i + 1 - j])
                dp[i + mArr - j] = min(dp[i + mArr - j], dp[i] + 1);
        }
    }

    return (dp[nArr] >= 1e9) ? -1 : dp[nArr];
}

int minimumInstructions(int _N, int _M, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B) {
    nArr = _N, mArr = _M, numCol = _K;
    for (int i = 1; i <= nArr; ++i) {
        colNeed[i] = _C[i - 1];
        C[i].clear();
    }

    int maxf(0);
    for (int i = 0; i < mArr; ++i) {
        int szlike(_A[i]);

        B[i].clear();
        for (int j = 0; j < szlike; ++j) {
            B[i].push_back(_B[i][j]);
            C[_B[i][j]].push_back(i);
            maxf = max(maxf, sz(C[_B[i][j]]));
        }
    }

    //if(sub3() != sub4()) exit(1); return -1;

    if(maxf <= 1)
        return sub1();

    if(nArr <= 500)
        return sub3();

    if(nArr <= 20000 && mArr <= 2000)
        return sub4();

    return -1;
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "paint"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> _A, _C;
    vector<vector<int>> _B;
    int _N, _M, _K;
    cin >> _N >> _M >> _K;

    _C.resize(_N);
    for (int i = 0; i < _N; ++i) {
        cin >> _C[i];
        _C[i] = Random(0, _K - 1); cout << _C[i] << " \n"[i + 1 == _N];
    }

    vector<int> col; for (int i = 0; i < _K; ++i) col.push_back(i);
    _A.resize(_M), _B.resize(_M);
    for (int i = 0; i < _M; ++i) {
        cin >> _A[i];
        _A[i] = Random(1, _K); cout << _A[i] << ' ';
        _B[i].resize(_A[i]);

        shuffle(col.begin(), col.end(), rng);
        for (int j = 0; j < _A[i]; ++j) {
            cin >> _B[i][j];
            _B[i][j] = col[j]; cout << _B[i][j] << " \n"[j + 1 == _A[i]];
        }
    }

    int ans = minimumInstructions(_N, _M, _K, _C, _A, _B);
    cout << "ANSWER: " << ans << '\n';

    return 0;
}

#endif // Nhoksocqt1

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37