oj.uz

Submission #495246

# Submission time Handle Problem Language Result Execution time Memory
495246 2021-12-18T07:50:59 Z Ierus Chessboard (IZhO18_chessboard) C++17
39 / 100
 2000 ms 5360 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 <= x / 2; ++i){
		if(x % i == 0){
			res.pb(i);
		}
	}
	return res;
}
vector<int> v[N];
struct block{
	int x, y;
	void read(){
		cin >> x >> y;
		cin >> x >> y;
		v[x].pb(y);
//		v.pb({x, y});
	}
}a[N];
//bool cmp(const pair<int,int> &a, const pair<int,int> &b){
//	if(a.F != b.F)
//		return a.F < b.F;
//	return a.S < b.S;
//}
int n, k;
int get(vector<int> &d, int res = LLONG_MAX){
	for(int i = 1; i <= n; ++i) sort(all(v[i]));
//	cerr << "V\n";
//	for(int i = 1; i <= n; ++i) {
//		if(sz(v[i])){
//			for(auto it : v[i])
//				cerr << i << ' ' << it << '\n';
//		}
//	}
//	d = {2};
	for(auto x : d){
		int sum1 = 0, sum2 = 0, cnt1 = 0, cnt2 = 0;
		bool ok = 1;
//		cerr << "X: " << x << '\n';
		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 = 0;
				for(int w = x1; w <= x2; ++w){
					int L = lower_bound(all(v[w]), y1) - v[w].begin();
					int R = upper_bound(all(v[w]), y2) - v[w].begin();
//					cerr << "w: " << w << " L: " << L << " R: " << R << "\n";
					cur += max(R-L,0LL);
				}
//				cerr << "x1: " << x1 << " y1: " << y1 << " x2: " << x2 << " y2: " << y2 << " cur: " << cur << '\n';
				if(ok & 1){
					sum1 += cur;
					cnt1 += x * x;
				}else{
					sum2 += cur;
					cnt2 += x * x;
				}			
				ok ^= 1;
			}
			if((n / x) % 2 == 0) ok ^= 1;
		}
		res = min({res, cnt1 - sum1 + sum2, cnt2 - sum2 + sum1});
	}
	return res;
}
main(){
	cin >> n >> k;
	for(int i = 1; i <= k; ++i){
		a[i].read();	
	}
	vector<int> d = div(n);
	cout << get(d) << '\n';
};

Compilation message

chessboard.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main(){
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2097 ms 4808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2608 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 4 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2636 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2608 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 4 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2636 KB Output is correct
16 Correct 51 ms 3424 KB Output is correct
17 Correct 117 ms 5032 KB Output is correct
18 Correct 116 ms 5276 KB Output is correct
19 Correct 200 ms 5132 KB Output is correct
20 Correct 254 ms 5360 KB Output is correct
21 Correct 88 ms 5040 KB Output is correct
22 Correct 9 ms 2636 KB Output is correct
23 Correct 76 ms 3764 KB Output is correct
24 Correct 121 ms 5192 KB Output is correct
25 Correct 28 ms 2864 KB Output is correct
26 Correct 88 ms 4164 KB Output is correct
27 Correct 110 ms 4676 KB Output is correct
28 Correct 126 ms 5228 KB Output is correct
29 Correct 46 ms 3532 KB Output is correct
30 Correct 14 ms 2636 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2097 ms 4808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Execution timed out 2097 ms 4808 KB Time limit exceeded
10 Halted 0 ms 0 KB -