Submission #951507

#	Time	Username	Problem	Language	Result	Execution time	Memory
951507		Nhoksocqt1	Painting Walls (APIO20_paint)	C++17	63 / 100	1586 ms	340840 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<ii> D[MAXN];
vector<int> B[MAXM], C[MAXN];
int dp[2 * MAXN], sum[MAXN], *f[MAXN];
int colNeed[MAXN], nArr, mArr, numCol;
bool dx[2003][MAXN], 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;
        }
    }

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

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

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

    return res;
}

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 = 0; i <= nArr + 1; ++i) {
        f[i] = new int[mArr + 2];
        for (int j = 0; j <= mArr + 1; ++j)
            f[i][j] = 0;
    }

    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) {
        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;
        }
    }

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

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

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

    return res;
}

queue<ii> qu[MAXN];
int magicFunc(void) {
    for (int i = 1; i <= nArr; ++i)
        sort(C[colNeed[i]].begin(), C[colNeed[i]].end());

    for (int i = 1; i + mArr - 1 <= nArr; ++i) {
        f[i] = new int[sz(C[colNeed[i]])];
        int k(0);
        while(k < sz(C[colNeed[i]]) && i - C[colNeed[i]][k] + mArr > nArr)
            ++k;

        if(k < sz(C[colNeed[i]])) {
            int id(C[colNeed[i]][k]);
            qu[i - id + mArr].push(ii(i, k));
        }

        for (int it = 0; it < sz(C[colNeed[i]]); ++it)
            f[i][it] = 0;
    }

    for (int i = 0; i <= nArr + mArr; ++i)
        dp[i] = 0;

    for (int i = nArr; i > 0; --i) {
        for (int j = 0; j < sz(C[colNeed[i]]); ++j) {
            int id(C[colNeed[i]][j]);
            ++dp[i - id + mArr];
        }

        if(i + mArr - 1 <= nArr) {
            for (int it = 0; it < sz(C[colNeed[i]]); ++it) {
                int id(C[colNeed[i]][it]);
                f[i][it] += dp[i - id + mArr];
            }
        }

        if(i > mArr) {
            for (int it = 0; it < sz(C[colNeed[i - mArr]]); ++it) {
                int id(C[colNeed[i - mArr]][it]);
                f[i - mArr][it] -= dp[i - id + mArr];
            }
        }

        while(sz(qu[i])) {
            int j(qu[i].front().fi), k(qu[i].front().se);
            qu[i].pop();

            f[j][k] += dp[i + mArr];
            if(++k < sz(C[colNeed[j]])) {
                int id(C[colNeed[j]][k]);
                qu[j - id + mArr].push(ii(j, k));
            }
        }
    }

    for (int i = 1; i + mArr - 1 <= nArr; ++i) {
        for (int it = 0; it < sz(C[colNeed[i]]); ++it)
            ok[i] |= (f[i][it] == mArr);
    }

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

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

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

    return res;
}

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(maxf <= 1)
        return sub1();

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

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

    return magicFunc();
}

#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: 23 / 23
• Subtask 5: 0 / 37