Submission #1294719


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[1000000 + 10][7];
bool used[1000000 + 10][7];

void paint(int base, int mm) {
    for (int i = 0; i < mm; ++ i) {
        if (vis[i % m]) {
            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;
    }

    int mm = m;
    if (m % 7) mm *= 7;

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

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

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

Submission Info

Submission Time
Task C - Calendar 2
User comsyl
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1824 Byte
Status AC
Exec Time 60 ms
Memory 21888 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 4 ms 8448 KB
sub0_in2.txt AC 4 ms 8448 KB
sub1_in1.txt AC 4 ms 8448 KB
sub1_in2.txt AC 4 ms 8448 KB
sub1_in3.txt AC 4 ms 8448 KB
sub1_in4.txt AC 4 ms 8448 KB
sub1_in5.txt AC 58 ms 21888 KB
sub2_in1.txt AC 35 ms 8576 KB
sub3_in1.txt AC 18 ms 8576 KB
sub3_in2.txt AC 12 ms 12928 KB
sub4_in1.txt AC 60 ms 11520 KB
sub4_in2.txt AC 36 ms 17408 KB