oj.uz

Submission #493355

# Submission time Handle Problem Language Result Execution time Memory
493355 2021-12-11T06:51:48 Z irmuun Chessboard (IZhO18_chessboard) C++17
16 / 100
 97 ms 3024 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-i)*(n+i)/2;
        w=b+(i*i);
    }
    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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 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 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 2232 KB Output is correct
2 Correct 16 ms 716 KB Output is correct
3 Correct 41 ms 1516 KB Output is correct
4 Correct 43 ms 1608 KB Output is correct
5 Correct 58 ms 2028 KB Output is correct
6 Correct 36 ms 1324 KB Output is correct
7 Correct 8 ms 460 KB Output is correct
8 Correct 51 ms 1396 KB Output is correct
9 Correct 97 ms 3024 KB Output is correct
10 Correct 52 ms 1804 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 70 ms 2232 KB Output is correct
2 Correct 16 ms 716 KB Output is correct
3 Correct 41 ms 1516 KB Output is correct
4 Correct 43 ms 1608 KB Output is correct
5 Correct 58 ms 2028 KB Output is correct
6 Correct 36 ms 1324 KB Output is correct
7 Correct 8 ms 460 KB Output is correct
8 Correct 51 ms 1396 KB Output is correct
9 Correct 97 ms 3024 KB Output is correct
10 Correct 52 ms 1804 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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 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 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 70 ms 2232 KB Output is correct
10 Correct 16 ms 716 KB Output is correct
11 Correct 41 ms 1516 KB Output is correct
12 Correct 43 ms 1608 KB Output is correct
13 Correct 58 ms 2028 KB Output is correct
14 Correct 36 ms 1324 KB Output is correct
15 Correct 8 ms 460 KB Output is correct
16 Correct 51 ms 1396 KB Output is correct
17 Correct 97 ms 3024 KB Output is correct
18 Correct 52 ms 1804 KB Output is correct
19 Incorrect 1 ms 204 KB Output isn't correct
20 Halted 0 ms 0 KB -