Submission #1291895
Source Code Expand
#include<cstdio>
#include<vector>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using ll=long long;
const int white=-1;
const int black=100000000;
vi gx, gy;
void push(int x, int y)
{
gx.push_back(x);
gy.push_back(y);
}
int pop(int& x, int& y)
{
if(gx.size()<=0) return 0;
x=gx.back();
y=gy.back();
gx.pop_back();
gy.pop_back();
return 1;
}
void eng_fill(vvi& c, int x, int y, int g)
{
int vx[]={ 1, 0,-1, 0};
int vy[]={ 0,-1, 0, 1};
int nx, ny;
int w, h;
w=7;
h=c.size();
push(x, y);
c[y][x]=g;
while(pop(x, y))
{
for(int i=0;i<4;i++)
{
nx=x+vx[i];
ny=y+vy[i];
if(nx<0 || w<=nx || ny<0 || h<=ny) continue;
if(c[ny][nx]!=white) continue;
c[ny][nx]=g;
push(nx, ny);
}
}
}
int engroup(vvi& c)
{
int w, h, x, y;
int g=0;
w=7;
h=c.size();
for(y=0;y<h;y++)
{
for(x=0;x<w;x++)
{
if(c[y][x]!=white) continue;
eng_fill(c, x, y, g);
g++;
}
}
return g;
}
int gcd(int a, int b)
{
int c;
while((c=a%b))
{
a=b;
b=c;
}
return b;
}
int lcm(int a, int b)
{
return a/gcd(a, b)*b;
}
int main(void)
{
int m, q, g, uh, gc;
ll n, h;
vvi c, f;
while(scanf("%lld%d%d", &n, &m, &q)==3)
{
uh=lcm(m, 7)/7;
h=n/uh;
c.clear();
c.resize(uh);
for(auto& ce: c) ce.resize(7, white);
for(int i=0;i<q;i++)
{
int a;
scanf("%d", &a);
for(int j=a;j<uh*7;j+=m)
{
c[j/7][j%7]=black;
}
}
g=engroup(c);
f.clear();
for(int i=0;i<7;i++)
{
int u=c[0][i];
int l=c[uh-1][i];
int j;
if(u==black || l==black) continue;
if(u>l) swap(u, l);
vi ft={u,l};
for(j=f.size()-1;j>=0;j--)
{
if(ft==f[j]) break;
}
if(j<0)
{
f.push_back(ft);
// printf("%d %d\n", ft[0], ft[1]);
}
}
gc=f.size();
# if 0
for(auto ce:c)
{
for(int x:ce)
{
if(x==black) printf(" X ");
else printf("%2d ", x);
}
printf("\n");
}
printf("g=%d h=%d gc=%d\n", g, h, gc);
#endif
ll result=g*h-gc*(h-1);
printf("%lld\n", result);
}
return 0;
}
Submission Info
Submission Time
2017-05-17 18:47:43+0900
Task
C - Calendar 2
User
myanta
Language
C++14 (GCC 5.4.1)
Score
500
Code Size
2155 Byte
Status
AC
Exec Time
22 ms
Memory
8316 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:119:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
^
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
1 ms
256 KB
sub0_in2.txt
AC
1 ms
256 KB
sub1_in1.txt
AC
1 ms
256 KB
sub1_in2.txt
AC
1 ms
256 KB
sub1_in3.txt
AC
1 ms
256 KB
sub1_in4.txt
AC
1 ms
256 KB
sub1_in5.txt
AC
21 ms
8316 KB
sub2_in1.txt
AC
10 ms
1152 KB
sub3_in1.txt
AC
5 ms
1152 KB
sub3_in2.txt
AC
4 ms
1152 KB
sub4_in1.txt
AC
22 ms
7296 KB
sub4_in2.txt
AC
12 ms
4988 KB