Submission #1695968


Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

class UnionFind {
    int cnt;
    vector<int> par, rank, size;
public:
    UnionFind() {}
    UnionFind(int _n) :cnt(_n), par(_n), rank(_n), size(_n, 1) {
        for (int i = 0; i<_n; ++i) par[i] = i;
    }
    int find(int k) {
        return (k == par[k]) ? k : (par[k] = find(par[k]));
    }
    int operator[](int k) {
        return find(k);
    }
    int getSize(int k) {
        return size[find(k)];
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        --cnt;
        if (rank[x] < rank[y]) {
            par[x] = y;
            size[y] += size[x];
        } else {
            par[y] = x;
            size[x] += size[y];
            if (rank[y] == rank[x]) ++rank[x];
        }
    }
    int count() {
        return cnt;
    }
};

bool A[100000 * 7][7];
int f(int h, int m, vi &col) {
    MEM(A, 0);
    UnionFind uf(7 * h);
    int cur = 0, black = 0;
    rep(y, h)rep(x, 7) {
        if (!col[cur%m]) {
            A[y][x] = 1;
            if (y > 0 && A[y - 1][x])uf.unite(cur, cur - 7);
            if (x > 0 && A[y][x - 1])uf.unite(cur, cur - 1);
        } else {
            black++;
        }
        cur++;
    }
    return uf.count() - black;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    int m, q;
    cin >> n >> m >> q;
    vi col(m);
    rep(i, q) {
        int a;
        cin >> a;
        col[a] = 1;
    }

    int H = m;
    if (H % 7 == 0)H /= 7;
    int b = f(H, m, col), a = f(H * 2, m, col) - b;
    cout << a*((n - H) / H) + b << endl;
}

Submission Info

Submission Time
Task C - Calendar 2
User paruki
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2201 Byte
Status AC
Exec Time 41 ms
Memory 21872 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 100 / 100 90 / 90 200 / 200 110 / 110
Status
AC × 2
AC × 7
AC × 1
AC × 3
AC × 12
Set Name Test Cases
Sample sub0_in1.txt, sub0_in2.txt
Subtask1 sub0_in1.txt, sub0_in2.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub1_in5.txt
Subtask2 sub2_in1.txt
Subtask3 sub2_in1.txt, sub3_in1.txt, sub3_in2.txt
Subtask4 sub0_in1.txt, sub0_in2.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub1_in5.txt, sub2_in1.txt, sub3_in1.txt, sub3_in2.txt, sub4_in1.txt, sub4_in2.txt
Case Name Status Exec Time Memory
sub0_in1.txt AC 3 ms 4992 KB
sub0_in2.txt AC 3 ms 4992 KB
sub1_in1.txt AC 3 ms 4992 KB
sub1_in2.txt AC 3 ms 4992 KB
sub1_in3.txt AC 3 ms 4992 KB
sub1_in4.txt AC 3 ms 4992 KB
sub1_in5.txt AC 38 ms 21872 KB
sub2_in1.txt AC 12 ms 7428 KB
sub3_in1.txt AC 10 ms 7428 KB
sub3_in2.txt AC 7 ms 6992 KB
sub4_in1.txt AC 41 ms 21872 KB
sub4_in2.txt AC 24 ms 14728 KB