Submission #43887

#	Time	Username	Problem	Language	Result	Execution time	Memory
43887		Tenuun	Chessboard (IZhO18_chessboard)	C++17	8 / 100	95 ms	628 KiB

chessboard

#include<bits/stdc++.h>

using namespace std;

int main(){
	int n, k, x, y, x1, y1, res=INT_MAX;
	cin >> n >> k;
	vector<int>fac;
	map<int, int>map;
	for(int i=1; i<n; i++){
		if(n%i==0){
			fac.push_back(i);
		}
	}
	if(k==0){
		int res=(n*n)/2;
		int i=fac.size()-1;
		for(int i=fac.size()-1; i>=0; i--){
			if((n/fac[i])%2){	
				res=(n*n-fac[i]*fac[i])/2;	
				cout << res; return 0;
			}
		}
		cout << res;
		return 0;
	}
	for(int j=0; j<k; j++){
		cin >> x >> y >> x1 >> y1;
		for(int i=0; i<fac.size(); i++){
			map[i+1]=0;
			if((x%(2*fac[i])>=1 && x%(2*fac[i])<=fac[i] && y%(2*fac[i])<=fac[i]&&y%(2*fac[i])>=1) ||((x%(2*fac[i])==0 || x%(2*fac[i])>fac[i]) && (y%(2*fac[i])>fac[i]||y%(2*fac[i])==0)) )map[i+1]++;
		}
	}
	int i=0;
	for (auto it=map.begin(); it!=map.end(); ++it){
		int res1, res2;
		i=it->first-1;
		//cout << it->first << it->second << endl;
		if(n/fac[i]%2){	
			res1=(n*n-fac[i]*fac[i])/2+fac[i]*fac[i]-it->second+k-it->second;
			res2=it->second+(n*n-fac[i]*fac[i])/2-(k-it->second);
			res2=n*n-res1;
			//cout << it->second << " " << res1 << " " << res2 << endl;	
		}
		else{
			res1=(n*n)/2-it->second+k-it->second;
			res2=n*n-res1;
		}
		res=min(res, res1);
		res=min(res, res2);
		i++;
	}
	cout << res;
    return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:17:7: warning: unused variable 'i' [-Wunused-variable]
   int i=fac.size()-1;
       ^
chessboard.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<fac.size(); i++){
                ~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30