Submission #342667

#TimeUsernameProblemLanguageResultExecution timeMemory
342667IZhO_2021_I_want_SilverChessboard (IZhO18_chessboard)C++14
100 / 100
687 ms5996 KiB
#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> #include <map> #include <iomanip> #include <cassert> #include <stack> #include <queue> #include <deque> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp>- using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; // template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // order_of_key (k) : Number of items strictly smaller than k . // find_by_order(k) : K-th element in a set (counting from zero). #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define pb push_back #define ppb pop_back #define mkp make_pair #define F first #define S second #define lb lower_bound #define ub upper_bound #define show(a) cerr << #a <<" -> "<< a <<" " #define nl cerr <<"\n" #define int ll const int N = 2e5 + 5; const int oo = 1e18 + 5; int line(int len, int sz) { return (len / (sz * 2)) * sz + min(len % (sz * 2), sz); } int calc(int n, int m, int sz) { if (n < 0 || m < 0) { return 0; } int ln = n - line(n, sz), lm = m - line(m, sz); return line(n, sz) * line(m, sz) + ln * lm; } int n, k, ans = oo, x[N], y[N], x2[N], y2[N]; vector <int> vec; void solve() { cin >> n >> k; for (int i = 1; i <= k; ++i) { cin >> x[i] >> y[i] >> x2[i] >> y2[i]; } for (int sz = 1; sz < n; ++sz) { if (n % sz == 0) { vec.pb(sz); } } for (int sz : vec) { int res1 = calc(n, n, sz), res2 = (n * n) - res1; for (int i = 1; i <= k; ++i) { int b = calc(x2[i], y2[i], sz) - calc(x[i]-1, y2[i], sz) - calc(x2[i], y[i]-1, sz) + calc(x[i]-1, y[i]-1, sz); int w = (x2[i] - x[i] + 1) * (y2[i] - y[i] + 1) - b; res1 = res1 - b + w; res2 = res2 - w + b; } ans = min({ans, res1, res2}); } cout << ans; } main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int tests = 1; //cin >> tests; while (tests --) { solve(); } return 0; } /* Just Chalish! 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 */

Compilation message (stderr)

chessboard.cpp:75:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 |  main () {
      |        ^
#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...