oj.uz

Submission #493348

# Submission time Handle Problem Language Result Execution time Memory
493348 2021-12-11T06:45:19 Z irmuun Chessboard (IZhO18_chessboard) C++17
16 / 100
 90 ms 3092 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define PI 3.14159265359
ll n,m,t,p,h,a,b,c,d,e,f,i,j,k,r,l,mod=1000000007,mod1=998244353,MAX=1e18,ans;
ll X1[100001],X2[100001],Y1[100001],Y2[100001];
string s,u;
ll df[101];
vector<pair<ll,ll> >v;
vector<ll>dv[101];
void dfs(ll x){
    df[x]=1;
    for(ll i=0;i<dv[x].size();i++){
        if(df[dv[x][i]]==0){
            dfs(dv[x][i]);
        }
    }
}
ll fastPow(ll a,ll b){
    ll d=1;
    while(b>0){
        if(b%2==1){
            d=d*a%mod;
        }
        b/=2;
        a=a*a%mod;
    }
    return d;
}
ll check(){
    ll c=n/i;
    ll b,w;
    if(c%2==0){
        b=n*n/2;
        w=b;
    }
    else{
        b=(n-c)*(n+c)/2;
        w=b+(c*c);
    }
    ll num[2]={0};
    for(ll i=1;i<=k;i++){
        num[(((X1[i]-1)/c)+((Y1[i]-1)/c))%2]++;
    }
    return min((w-num[0])+num[1],(b-num[1])+num[0]);
}
int main(){
    cin>>n>>k;
    for(i=1;i<=k;i++){
        cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
    }
    if(k==0){
        ans=n*n/2;
        for(i=1;i<n;i++){
            if(n%i==0&&n/i%2==1){
                d=n*n-(i*i);
                ans=min(ans,d/2);
            }
        }
        cout<<ans;
        return 0;
    }
    p=0;
    for(i=2;i<=sqrt(n);i++){
        if(n%i==0){
            p=1;
            break;
        }
    }
    if(p==0){
        d=n*n/2;
        if(n==2){
            e=d;
        }
        else{
            e=d+1;
        }
        r=0;
        l=0;
        for(i=1;i<=k;i++){
            if((X1[i]+Y1[i])%2==0){
                r++;
            }
            else{
                l++;
            }
        }
        cout<<min((e-r)+l,(d-l)+r);
        return 0;
    }
    ans=n*n;
    for(i=1;i<n;i++){
        if(n%i==0){
            ans=min(ans,check());
        }
    }
    cout<<ans;
}

Compilation message

chessboard.cpp: In function 'void dfs(long long int)':
chessboard.cpp:16:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(ll i=0;i<dv[x].size();i++){
      |                ~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2136 KB Output is correct
2 Correct 16 ms 716 KB Output is correct
3 Correct 45 ms 1448 KB Output is correct
4 Correct 43 ms 1724 KB Output is correct
5 Correct 62 ms 1924 KB Output is correct
6 Correct 38 ms 1528 KB Output is correct
7 Correct 8 ms 460 KB Output is correct
8 Correct 39 ms 1360 KB Output is correct
9 Correct 90 ms 3092 KB Output is correct
10 Correct 72 ms 1836 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2136 KB Output is correct
2 Correct 16 ms 716 KB Output is correct
3 Correct 45 ms 1448 KB Output is correct
4 Correct 43 ms 1724 KB Output is correct
5 Correct 62 ms 1924 KB Output is correct
6 Correct 38 ms 1528 KB Output is correct
7 Correct 8 ms 460 KB Output is correct
8 Correct 39 ms 1360 KB Output is correct
9 Correct 90 ms 3092 KB Output is correct
10 Correct 72 ms 1836 KB Output is correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 68 ms 2136 KB Output is correct
10 Correct 16 ms 716 KB Output is correct
11 Correct 45 ms 1448 KB Output is correct
12 Correct 43 ms 1724 KB Output is correct
13 Correct 62 ms 1924 KB Output is correct
14 Correct 38 ms 1528 KB Output is correct
15 Correct 8 ms 460 KB Output is correct
16 Correct 39 ms 1360 KB Output is correct
17 Correct 90 ms 3092 KB Output is correct
18 Correct 72 ms 1836 KB Output is correct
19 Incorrect 1 ms 204 KB Output isn't correct
20 Halted 0 ms 0 KB -