제출 #1134429

#제출 시각아이디문제언어결과실행 시간메모리
1134429Halym2007Chessboard (IZhO18_chessboard)C++17
39 / 100
25 ms1864 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define sz size() #define ff first #define ss second #define pb push_back #define pii pair <int, int> #define dur exit(0) #define dur1 return(0) const int N = 2e5 + 5; int n, k1; pii p[N], q[N]; vector <ll> v; ll ans = 1e18, a[N]; int main () { // freopen ("input.txt", "r", stdin); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> k1; for (int i = 1; i < n; ++i) { if (n % i == 0) { v.pb (i); } } ll k = 0; for (int i = 1; i <= k1; ++i) { cin >> p[i].ff >> p[i].ss >> q[i].ff >> q[i].ss; k += (q[i].ff - p[i].ff + 1) * (q[i].ss - p[i].ss + 1); } // cout << "\n"; // for (int i = 1; i <= k1; ++i) { // cout << p[i].ff << " " << p[i].ss << " " << q[i].ff << " " << q[i].ss << "\n"; // } // cout << "\n\n\n"; for (ll bol : v) { // 1-nji ak bolsa for (int i = 1; i <= n; ++i) { a[i] = ((i + bol - 1) / bol) % 2; a[i] += a[i - 1]; } // ilki 1-nji block gara renkde bolsa shol variant-da seretyas ll jogap = 0, ak = 0; ll opyshy_gara = (a[n] * a[n]) + (n - a[n]) * (n - a[n]); for (int i = 1; i <= k1; ++i) { ll val1 = (a[q[i].ss] - a[p[i].ss - 1]) * (a[q[i].ff] - a[p[i].ff - 1]); ll val2 = (q[i].ss - p[i].ss + 1) - (a[q[i].ss] - a[p[i].ss - 1]); ll val3 = (q[i].ff - p[i].ff + 1) - (a[q[i].ff] - a[p[i].ff - 1]); val2 *= val3; ll val4 = (q[i].ff - p[i].ff + 1) * (q[i].ss - p[i].ss + 1); // if (p[i].ff == 3 and p[i].ff == 6) { // cout << "men->" << val1 << " " << val2 << " " << val4 << "\n"; // return 0; // } ak += val4 - (val2 + val1); } jogap = (opyshy_gara - k) + (ak * 2LL); // if (bol == 2) { // cout << opyshy_gara << " " << ak << " " << k << "\n"; // dur1; // } // indi gara etyas ak = 0; opyshy_gara = (n * n) - opyshy_gara; for (int i = 1; i <= k1; ++i) { ll val1 = (a[q[i].ss] - a[p[i].ss - 1]) * (a[q[i].ff] - a[p[i].ff - 1]); ll val2 = (q[i].ss - p[i].ss + 1) - (a[q[i].ss] - a[p[i].ss - 1]); ll val3 = (q[i].ff - p[i].ff + 1) - (a[q[i].ff] - a[p[i].ff - 1]); val2 *= val3; ll val4 = (q[i].ff - p[i].ff + 1) * (q[i].ss - p[i].ss + 1); ak += val2 + val1; } ll jogap1 = (opyshy_gara - k) + (ak * 2LL); ans = min ({ans, jogap, jogap1}); } cout << ans << "\n"; }
#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...