oj.uz

Submission #378540

# Submission time Handle Problem Language Result Execution time Memory
378540 2021-03-17T01:37:55 Z daniel920712 Chessboard (IZhO18_chessboard) C++14
8 / 100
 66 ms 8920 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 3 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 3 ms 4972 KB Output is correct
7 Correct 3 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 8920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5024 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 6 ms 5228 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Incorrect 4 ms 5100 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5024 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 6 ms 5228 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Incorrect 4 ms 5100 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 8920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 3 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 3 ms 4972 KB Output is correct
7 Correct 3 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Incorrect 66 ms 8920 KB Output isn't correct
10 Halted 0 ms 0 KB -