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 |
|
|
|
|
|
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 |