Submission #1294705

---

Source Code Expand

/***********************************************
#
#      Filename: c.cpp
#
#        Author: Comsyl - ylsong15@fudan.edu.cn
#   Description: ---
#        Create: 2017-05-19 23:53:20
***********************************************/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int m, q;
bool vis[100000 + 10];
bool bao[100000 + 10][7];
bool used[100000 + 10][7];

void paint(int base) {
    for (int i = 0; i < m; ++ i) {
        if (vis[i]) {
            int r = i / 7;
            int c = i % 7;
            bao[r + base][c] = true;
        }
    }
}

int dir[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
void dfs(int x, int y, int rmax) {
    used[x][y] = true;
    for (int i = 0; i < 4; ++ i) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx>=0 && nx<rmax && ny>=0 && ny<7 && !used[nx][ny] && !bao[nx][ny]) {
            dfs(nx, ny, rmax);
        }
    }
}

int main()
{
    cin >> n >> m >> q;
    int r;
    for (int i = 0; i < q; ++ i) {
        cin >> r;
        vis[r] = true;
    }

    paint(0);
    int count1 = 0;
    for (int i = 0; i < m/7; ++ i) {
        for (int j = 0; j < 7; ++ j) {
            if (!bao[i][j] && !used[i][j]) {
                dfs(i, j, m/7);
                ++ count1;
            }
        }
    }

    paint(m/7);
    int count2 = 0;
    memset(used, false, sizeof(used));
    for (int i = 0; i < 2*m/7; ++ i) {
        for (int j = 0; j < 7; ++ j) {
            if (!bao[i][j] && !used[i][j]) {
                dfs(i, j, 2*m/7);
                ++ count2;
            }
        }
    }

    cout << count1 * 1L + (count2 - count1) * 1L * (n / (m/7) - 1L) << endl;
    return 0;
}

Submission Info

Judge Result