oj.uz

Submission #495182

# Submission time Handle Problem Language Result Execution time Memory
495182 2021-12-18T06:14:42 Z Ierus Chessboard (IZhO18_chessboard) C++17
31 / 100
 2000 ms 20796 KB 
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define int long long
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e5+777;
const int MOD = 1e9+7;
vector<int> div(int x){
	vector<int> res = {1};
	for(int i = 2; i * i <= x; ++i){
		if(x % i == 0){
			res.pb(i);
			if(x / i != i)	
				res.pb(x/i);
		}
	}
	sort(all(res));
	return res;
}
struct block{
	int x1, y1, x2, y2;
	void read(){
		cin >> x1 >> y1 >> x2 >> y2;
	}
}a[N];
int n, k;
int get1(){
	int b[N][2]{};
	for(int i = 1; i <= k; ++i){
		++b[a[i].x1][a[i].y1&1];
	}
	int cnt1 = n * n / 2 + (n & 1);
	int cnt2 = n * n - cnt1;
	int sum1 = 0, sum2 = 0;
	for(int i = 1; i <= n; ++i){
		if(i & 1){
			sum1 += b[i][1];
			sum2 += b[i][0];
		}else{
			sum1 += b[i][0];
			sum2 += b[i][1];
		}
	}
	return min(cnt1 - sum1 + sum2, cnt2 - sum2 + sum1);
}
int pref[1111][1111], ar[1111][1111];
void precalc(){
	for(int l = 1; l <= k; ++l){
		ar[a[l].x1][a[l].y1] = 1;
	}
	pref[1][1] = ar[1][1];
    for(int i = 2; i <= n; i++) {
        pref[i][1] = pref[i-1][1] + ar[i][1];
    }
    for(int i = 2; i <= n; i++) {
        pref[1][i] = pref[1][i-1] + ar[1][i];
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + ar[i][j];
        }
    }
//    cerr << "array\n";
//    for(int i = 1; i <= n; ++i){
//    	for(int j = 1; j <= n; ++j){
//    		cerr << ar[i][j] << ' ';
//		}cerr << '\n';
//	}cerr << '\n';
//	cerr << "pref\n";
//    for(int i = 1; i <= n; ++i){
//    	for(int j = 1; j <= n; ++j){
//    		cerr << pref[i][j] << ' ';
//		}cerr << '\n';
//	}cerr << '\n';
}
long long query(int x1, int y1, int x2, int y2) {
    return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
}
int get2(vector<int> &d, int res = LLONG_MAX){
	precalc();
	for(auto x : d){
		int sum1 = 0, sum2 = 0, cnt1 = 0, cnt2 = 0;
		bool ok = 1;
		for(int i = 1; i <= n; i += x){
			for(int j = 1; j <= n; j += x){
				int x1 = i, y1 = j, x2 = i + x - 1, y2 = j + x - 1;
				int cur = query(x1, y1, x2, y2);
				cerr << i << ' ' << j << ": " << ok << '\n';
				if(ok & 1){
					sum1 += cur;
					cnt1 += x * x;
				}else{
					sum2 += cur;
					cnt2 += x * x;
				}
				ok ^= 1;
			}
			if((n / x) % 2 == 0) ok ^= 1;
//			cerr <<"2i: " << i << " ok: " << ok << '\n';
		}
//		cerr << "X: " << x << " cnt1: " << cnt1 << " sum1: " << sum1 <<  " cnt2: " << cnt2 << " sum2: " << sum2 << '\n';
	res = min({res, cnt1 - sum1 + sum2, cnt2 - sum2 + sum1});
	}
	return res;
}
signed main(){auto solve=[&](){
	cin >> n >> k;
	for(int i = 1; i <= k; ++i){
		a[i].read();
	}
	vector<int> d = div(n);
//	cerr << "D: ";for(auto it : d){
//		cerr << it << ' ';
//	}cerr << '\n';
	if(sz(d) == 1){
		cout << get1() << '\n';	
	}else{
		cout << get2(d);
	}
};NFS;solve();}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 97 ms 844 KB Output is correct
3 Correct 85 ms 860 KB Output is correct
4 Correct 85 ms 836 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 104 ms 812 KB Output is correct
7 Correct 67 ms 796 KB Output is correct
8 Correct 77 ms 796 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3788 KB Output is correct
2 Correct 6 ms 2420 KB Output is correct
3 Correct 14 ms 3132 KB Output is correct
4 Correct 13 ms 3296 KB Output is correct
5 Correct 17 ms 3516 KB Output is correct
6 Correct 12 ms 2892 KB Output is correct
7 Correct 3 ms 2124 KB Output is correct
8 Correct 11 ms 2892 KB Output is correct
9 Correct 28 ms 4676 KB Output is correct
10 Correct 17 ms 3356 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1068 KB Output is correct
2 Correct 50 ms 776 KB Output is correct
3 Correct 65 ms 972 KB Output is correct
4 Correct 60 ms 1104 KB Output is correct
5 Correct 46 ms 1120 KB Output is correct
6 Correct 55 ms 1052 KB Output is correct
7 Correct 64 ms 1224 KB Output is correct
8 Correct 34 ms 932 KB Output is correct
9 Correct 80 ms 1240 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 33 ms 956 KB Output is correct
12 Correct 1 ms 1868 KB Output is correct
13 Correct 44 ms 972 KB Output is correct
14 Correct 56 ms 1104 KB Output is correct
15 Correct 21 ms 716 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1068 KB Output is correct
2 Correct 50 ms 776 KB Output is correct
3 Correct 65 ms 972 KB Output is correct
4 Correct 60 ms 1104 KB Output is correct
5 Correct 46 ms 1120 KB Output is correct
6 Correct 55 ms 1052 KB Output is correct
7 Correct 64 ms 1224 KB Output is correct
8 Correct 34 ms 932 KB Output is correct
9 Correct 80 ms 1240 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 33 ms 956 KB Output is correct
12 Correct 1 ms 1868 KB Output is correct
13 Correct 44 ms 972 KB Output is correct
14 Correct 56 ms 1104 KB Output is correct
15 Correct 21 ms 716 KB Output is correct
16 Execution timed out 2079 ms 20796 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3788 KB Output is correct
2 Correct 6 ms 2420 KB Output is correct
3 Correct 14 ms 3132 KB Output is correct
4 Correct 13 ms 3296 KB Output is correct
5 Correct 17 ms 3516 KB Output is correct
6 Correct 12 ms 2892 KB Output is correct
7 Correct 3 ms 2124 KB Output is correct
8 Correct 11 ms 2892 KB Output is correct
9 Correct 28 ms 4676 KB Output is correct
10 Correct 17 ms 3356 KB Output is correct
11 Correct 75 ms 1068 KB Output is correct
12 Correct 50 ms 776 KB Output is correct
13 Correct 65 ms 972 KB Output is correct
14 Correct 60 ms 1104 KB Output is correct
15 Correct 46 ms 1120 KB Output is correct
16 Correct 55 ms 1052 KB Output is correct
17 Correct 64 ms 1224 KB Output is correct
18 Correct 34 ms 932 KB Output is correct
19 Correct 80 ms 1240 KB Output is correct
20 Correct 1 ms 1868 KB Output is correct
21 Correct 33 ms 956 KB Output is correct
22 Correct 1 ms 1868 KB Output is correct
23 Correct 44 ms 972 KB Output is correct
24 Correct 56 ms 1104 KB Output is correct
25 Correct 21 ms 716 KB Output is correct
26 Execution timed out 2079 ms 20796 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 97 ms 844 KB Output is correct
3 Correct 85 ms 860 KB Output is correct
4 Correct 85 ms 836 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 104 ms 812 KB Output is correct
7 Correct 67 ms 796 KB Output is correct
8 Correct 77 ms 796 KB Output is correct
9 Correct 18 ms 3788 KB Output is correct
10 Correct 6 ms 2420 KB Output is correct
11 Correct 14 ms 3132 KB Output is correct
12 Correct 13 ms 3296 KB Output is correct
13 Correct 17 ms 3516 KB Output is correct
14 Correct 12 ms 2892 KB Output is correct
15 Correct 3 ms 2124 KB Output is correct
16 Correct 11 ms 2892 KB Output is correct
17 Correct 28 ms 4676 KB Output is correct
18 Correct 17 ms 3356 KB Output is correct
19 Correct 75 ms 1068 KB Output is correct
20 Correct 50 ms 776 KB Output is correct
21 Correct 65 ms 972 KB Output is correct
22 Correct 60 ms 1104 KB Output is correct
23 Correct 46 ms 1120 KB Output is correct
24 Correct 55 ms 1052 KB Output is correct
25 Correct 64 ms 1224 KB Output is correct
26 Correct 34 ms 932 KB Output is correct
27 Correct 80 ms 1240 KB Output is correct
28 Correct 1 ms 1868 KB Output is correct
29 Correct 33 ms 956 KB Output is correct
30 Correct 1 ms 1868 KB Output is correct
31 Correct 44 ms 972 KB Output is correct
32 Correct 56 ms 1104 KB Output is correct
33 Correct 21 ms 716 KB Output is correct
34 Execution timed out 2079 ms 20796 KB Time limit exceeded
35 Halted 0 ms 0 KB -