oj.uz

Submission #378555

# Submission time Handle Problem Language Result Execution time Memory
378555 2021-03-17T01:43:40 Z daniel920712 Chessboard (IZhO18_chessboard) C++14
39 / 100
 1308 ms 36844 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <set>

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];
set < pair < long long , long long > > vis;
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++)
            {
                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;
                    //printf("%lld %lld %lld %lld %lld\n",i,j,k,x,y);
                    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==0) 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:16:27: warning: unused variable 't' [-Wunused-variable]
   16 |     long long N,M,ans=2e9,t,a,b,c,d,i,j,k,x,y;
      |                           ^
chessboard.cpp:16:41: warning: unused variable 'k' [-Wunused-variable]
   16 |     long long N,M,ans=2e9,t,a,b,c,d,i,j,k,x,y;
      |                                         ^
chessboard.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |     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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 3 ms 4972 KB Output is correct
3 Correct 4 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 4 ms 4972 KB Output is correct
7 Correct 4 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 Correct 116 ms 12908 KB Output is correct
2 Correct 25 ms 7148 KB Output is correct
3 Incorrect 66 ms 10476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 6 ms 5228 KB Output is correct
5 Correct 5 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Correct 5 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 5 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 5 ms 5228 KB Output is correct
14 Correct 6 ms 5228 KB Output is correct
15 Correct 5 ms 5228 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 6 ms 5228 KB Output is correct
5 Correct 5 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Correct 5 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 5 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 5 ms 5228 KB Output is correct
14 Correct 6 ms 5228 KB Output is correct
15 Correct 5 ms 5228 KB Output is correct
16 Correct 65 ms 10220 KB Output is correct
17 Correct 172 ms 16384 KB Output is correct
18 Correct 308 ms 20332 KB Output is correct
19 Correct 1094 ms 34760 KB Output is correct
20 Correct 1308 ms 36844 KB Output is correct
21 Correct 163 ms 15724 KB Output is correct
22 Correct 6 ms 5356 KB Output is correct
23 Correct 182 ms 15212 KB Output is correct
24 Correct 284 ms 19180 KB Output is correct
25 Correct 29 ms 7148 KB Output is correct
26 Correct 165 ms 14188 KB Output is correct
27 Correct 286 ms 20588 KB Output is correct
28 Correct 337 ms 22764 KB Output is correct
29 Correct 54 ms 9452 KB Output is correct
30 Correct 8 ms 5612 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 12908 KB Output is correct
2 Correct 25 ms 7148 KB Output is correct
3 Incorrect 66 ms 10476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 3 ms 4972 KB Output is correct
3 Correct 4 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 4 ms 4972 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Correct 116 ms 12908 KB Output is correct
10 Correct 25 ms 7148 KB Output is correct
11 Incorrect 66 ms 10476 KB Output isn't correct
12 Halted 0 ms 0 KB -