oj.uz

Submission #493335

# Submission time Handle Problem Language Result Execution time Memory
493335 2021-12-11T06:18:37 Z irmuun Chessboard (IZhO18_chessboard) C++17
16 / 100
 92 ms 5316 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;
}
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;//tegsh
		if(n==2){
			e=d;//sondgoi
		}
		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);
	}
}

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 1 ms 204 KB Output is correct
2 Correct 0 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 70 ms 2224 KB Output is correct
2 Correct 16 ms 1068 KB Output is correct
3 Correct 43 ms 2392 KB Output is correct
4 Correct 46 ms 2500 KB Output is correct
5 Correct 58 ms 3244 KB Output is correct
6 Correct 42 ms 2128 KB Output is correct
7 Correct 8 ms 688 KB Output is correct
8 Correct 38 ms 2216 KB Output is correct
9 Correct 92 ms 5316 KB Output is correct
10 Correct 51 ms 2988 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 2224 KB Output is correct
2 Correct 16 ms 1068 KB Output is correct
3 Correct 43 ms 2392 KB Output is correct
4 Correct 46 ms 2500 KB Output is correct
5 Correct 58 ms 3244 KB Output is correct
6 Correct 42 ms 2128 KB Output is correct
7 Correct 8 ms 688 KB Output is correct
8 Correct 38 ms 2216 KB Output is correct
9 Correct 92 ms 5316 KB Output is correct
10 Correct 51 ms 2988 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 1 ms 204 KB Output is correct
2 Correct 0 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 70 ms 2224 KB Output is correct
10 Correct 16 ms 1068 KB Output is correct
11 Correct 43 ms 2392 KB Output is correct
12 Correct 46 ms 2500 KB Output is correct
13 Correct 58 ms 3244 KB Output is correct
14 Correct 42 ms 2128 KB Output is correct
15 Correct 8 ms 688 KB Output is correct
16 Correct 38 ms 2216 KB Output is correct
17 Correct 92 ms 5316 KB Output is correct
18 Correct 51 ms 2988 KB Output is correct
19 Incorrect 1 ms 204 KB Output isn't correct
20 Halted 0 ms 0 KB -