Submission #378540

#	Time	Username	Problem	Language	Result	Execution time	Memory
378540		daniel920712	Chessboard (IZhO18_chessboard)	C++14	8 / 100	66 ms	8920 KiB

chessboard

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>

using namespace std;
vector < long long > have;
long long con1[100005];
long long con2[100005];
map < pair < long long , long long > , long long > con[100005];
int main()
{
    long long N,M,ans=2e9,t,a,b,c,d,i,j,k,x,y;
    scanf("%lld %lld",&N,&M);
    for(i=1;i<N;i++)
    {
        if(N%i==0)
        {
            have.push_back(i);
            con1[i]=(N/i)*(N/i)/2;
            con2[i]=(N/i)*(N/i)/2+(N/i)*(N/i)%2;
            //printf("%lld %lld %lld\n",i,con1[i],con2[i]);
        }
    }
    while(M--)
    {
        scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
        for(i=a;i<=c;i++)
        {
            for(j=b;j<=d;j++)
            {
                for(auto k:have)
                {
                    x=(i-1)/k;
                    y=(j-1)/k;
                    if((x+y)%2)
                    {
                        if(con[k].find(make_pair(x,y))==con[k].end()) con1[k]--;
                        con[k][make_pair(x,y)]++;
                    }
                    else
                    {
                        if(con[k].find(make_pair(x,y))==con[k].end()) con2[k]--;
                        con[k][make_pair(x,y)]++;
                    }
                }
            }
        }
    }
    for(auto i:have)
    {
        a=con1[i]*i*i;
        for(auto j:con[i])
        {
            if((j.first.first+j.first.second)%2) a+=i*i-j.second;
            else a+=j.second;
        }
        ans=min(ans,a);

        a=con2[i]*i*i;
        for(auto j:con[i])
        {
            if((j.first.first+j.first.second)%2==1) a+=i*i-j.second;
            else a+=j.second;
        }
        ans=min(ans,a);

    }



    printf("%lld\n",ans);
    return 0;
}
/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:14:27: warning: unused variable 't' [-Wunused-variable]
   14 |     long long N,M,ans=2e9,t,a,b,c,d,i,j,k,x,y;
      |                           ^
chessboard.cpp:14:41: warning: unused variable 'k' [-Wunused-variable]
   14 |     long long N,M,ans=2e9,t,a,b,c,d,i,j,k,x,y;
      |                                         ^
chessboard.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |     scanf("%lld %lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
chessboard.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |         scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30