Submission #342875

#TimeUsernameProblemLanguageResultExecution timeMemory
342875RakhmandChessboard (IZhO18_chessboard)C++14
70 / 100
487 ms3564 KiB
// // main.cpp // torelax // // Created by Rakhman on 11/15/20. // #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <queue> #include <cmath> #include <cstdlib> #include <ctime> #include <cassert> #include <iterator> #define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0); #define S second #define F first #define pb push_back #define nl '\n' #define NL cout << '\n'; #define EX exit(0) #define all(s) s.begin(), s.end() #define no_answer {cout << "NO"; exit(0);} #define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k) const long long mxn = 1e5 + 110; const long long mnn = 1e3 + 2; const long long mod = 1e9 + 7; const long long inf = 1e18; const long long OO = 1e9; typedef long long llong; typedef unsigned long long ullong; using namespace std; llong n, k; llong ans = inf; struct dot{ llong left, up, right, down; }b[mxn]; llong get_color(llong x, llong y, llong d){ return (((x - 1) / d) + ((y - 1) / d)) % 2; } llong get(llong d){ //left-corner is black llong blacks = d * d * (n / d) * (n / d / 2); if((n / d) % 2 == 1){ blacks += d * d * (n / d / 2 + 1); } llong paint = 0; llong blacks1 = n * n - blacks; for(int i = 1; i <= k; i++){ int x = b[i].left, y = b[i].up; if(get_color(x, y, d) == 0){ blacks--; }else{ paint++; } } //left-corner is white llong paint1 = 0; for(int i = 1; i <= k; i++){ int x = b[i].left, y = b[i].up; if(get_color(x, y, d) == 1){ blacks1--; }else{ paint1++; } } return min(blacks1 + paint1, blacks + paint); } int main() { ios; cin >> n >> k; for(int i = 1; i <= k; i++){ cin >> b[i].left >> b[i].up >> b[i].right >> b[i].down; } for(int i = 1; i <= sqrt(n); i++){ if(n % i == 0){ ans = min(ans, get(i)); if(n / i != i && i != 1){ ans = min(get(n / i), ans); } } } cout << ans; } /* 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...