Submission #378581

#	Time	Username	Problem	Language	Result	Execution time	Memory
378581		daniel920712	Chessboard (IZhO18_chessboard)	C++14	70 / 100	1854 ms	262148 KiB

chessboard

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

using namespace std;
vector < long long > have;
long long con1[100005];
long long con2[100005];
vector < pair < long long , long long > > con[100005];
set < pair < long long , long long > > vis;
int main()
{
    long long N,M,ans=1e18,t,a,b,c,d,i,j,k,x,y,m,n;
    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;
        }
    }
    while(M--)
    {
        scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
        for(i=a;i<=c;i++)
        {
            for(j=b;j<=d;j++)
            {
                if(vis.find(make_pair(i,j))!=vis.end()) continue;
                vis.insert(make_pair(i,j));
                for(auto k:have)
                {
                    x=(i-1)/k;
                    y=(j-1)/k;
                    con[k].push_back(make_pair(x,y));
                }
            }
        }
    }
    for(auto i:have)
    {
        sort(con[i].begin(),con[i].end());
        M=con[i].size();
        x=y=0;
        m=n=0;
        for(j=0;j<M;j++)
        {
            if(j==0||con[i][j]!=con[i][j-1])
            {
                if((con[i][j].first+con[i][j].second)%2)
                {
                    con1[i]--;
                    x++;
                }
                else
                {
                    con2[i]--;
                    y++;
                }
            }
            if((con[i][j].first+con[i][j].second)%2) m++;
            else n++;
        }
        a=con1[i]*i*i;
        a+=x*i*i-m;
        a+=n;

        ans=min(ans,a);

        a=con2[i]*i*i;
        a+=y*i*i-n;
        a+=m;
        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:17:28: warning: unused variable 't' [-Wunused-variable]
   17 |     long long N,M,ans=1e18,t,a,b,c,d,i,j,k,x,y,m,n;
      |                            ^
chessboard.cpp:17:42: warning: unused variable 'k' [-Wunused-variable]
   17 |     long long N,M,ans=1e18,t,a,b,c,d,i,j,k,x,y,m,n;
      |                                          ^
chessboard.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     scanf("%lld %lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
chessboard.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |         scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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