oj.uz

Submission #638149

# Submission time Handle Problem Language Result Execution time Memory
638149 2022-09-04T18:51:25 Z jcelin Sateliti (COCI20_satellti) C++14
110 / 110
 631 ms 37760 KB 
#include <bits/stdc++.h>
//#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 long double ld;
typedef unsigned int ui;

#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vLL>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 2e3 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;

char mat[MAXN][MAXN];
int sum[MAXN][MAXN], a[MAXN][MAXN];
int b1[MAXN], b2[MAXN], n, m;
int inv1[MAXN], inv2[MAXN];

int add(ll a, ll b){
	return (a + b) % mod;
}

int mul(ll a, ll b){
	return (a * b) % mod;
}

int sub(ll a, ll b){
	return (a - b + mod) % mod;
}

int exp(ll b, ll e){
	int ret = 1;
	while(e){
		if(e % 2) ret = mul(ret, b);
		b = mul(b, b);
		e /= 2;
	}
	return ret;
}

int divide(ll a, ll b){
	return mul(a, exp(b, mod - 2));
}

int calc(int r1, int s1, int r2, int s2){
	int val = sum[r2][s2];
	val = add(val, sum[r1 - 1][s1 - 1]);
	val = sub(val, add(sum[r2][s1 - 1], sum[r1 - 1][s2]));
	val = mul(val, mul(inv1[r1], inv2[s1]));
	return val;
}


//is (i, j) better than (x, y)
bool bs(int x, int y, int i, int j){
	if(calc(x, y, x + n - 1, y + m - 1) == calc(i, j, i + n - 1, j + m - 1)) return 0;
	//return 0;
	
	/*
	for(int dx=0; dx<n; dx++) for(int dy=0; dy<m; dy++){
		if(mat[x + dx][y + dy] > mat[i + dx][j + dy]) return 1;
		if(mat[x + dx][y + dy] < mat[i + dx][j + dy]) return 0;
	}
	*/
	
	int sx = 0, sy = 0;
	//2 bin searcha
	
	//
	int lo = 0, hi = n - 1, ret = -1;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(calc(x, y, x + mid, y + m - 1) != calc(i, j, i + mid, j + m - 1)) ret = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	sx = ret;
	
	
	lo = 0, hi = m - 1, ret = -1;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(calc(x, y, x + sx, y + mid) != calc(i, j, i + sx, j + mid)) ret = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	sy = ret;
	
	return mat[i + sx][j + sy] < mat[x + sx][y + sy];
}

void solve(){
	cin >> n >> m;
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> mat[i][j];
	
	for(int px=0; px<2; px++) for(int py=0; py<2; py++){
		for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
			mat[i + px * n][j + py * m] = mat[i][j];	
			a[i + px * n][j + py * m] = (mat[i][j] == '.');
		}			
	}
	
	
	b1[0] = 1, b2[0] = 1;
	for(int i=1; i<=2*max(n, m); i++) b1[i] = mul(b1[i - 1], 2), b2[i] = mul(b2[i - 1], 3);
	 
	inv1[2 * max(n, m)] = divide(1, b1[2 * max(n, m)]);
	inv2[2 * max(n, m)] = divide(1, b2[2 * max(n, m)]);
	for(int i=2 * max(n, m) - 1; i>=0; i--) inv1[i] = mul(inv1[i + 1], 2), inv2[i] = mul(inv2[i + 1], 3);
	
	for(int i=1; i<=2*n; i++) for(int j=1; j<=2*m; j++){
		a[i][j] = mul(a[i][j], mul(b1[i], b2[j]));
		sum[i][j] = add(sum[i - 1][j], add(a[i][j], sum[i][j - 1]));
		sum[i][j] = sub(sum[i][j], sum[i - 1][j - 1]);
	} 
	
	int x = 1, y = 1;
	for(int i=1; i<=2*n; i++){
		for(int j=1; j<=2*m; j++){
			if(i + n - 1 > 2 * n) continue;
			if(j + m - 1 > 2 * m) continue;
			//cout << i << " " << j << '\n';
			if(bs(x, y, i, j)) x = i, y = j;
			//cout << x << " " << y << "\n";
		}
	}
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++) cout << mat[i + x][j + y];
		cout << "\n";
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--)solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1224 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 2 ms 1360 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1224 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 2 ms 1360 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 49 ms 8900 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 6228 KB Output is correct
11 Correct 44 ms 8900 KB Output is correct
12 Correct 57 ms 9148 KB Output is correct
13 Correct 65 ms 9284 KB Output is correct
14 Correct 57 ms 9284 KB Output is correct
15 Correct 53 ms 9212 KB Output is correct
16 Correct 51 ms 9284 KB Output is correct
17 Correct 52 ms 9192 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1224 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 2 ms 1360 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 49 ms 8900 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 6228 KB Output is correct
11 Correct 44 ms 8900 KB Output is correct
12 Correct 57 ms 9148 KB Output is correct
13 Correct 65 ms 9284 KB Output is correct
14 Correct 57 ms 9284 KB Output is correct
15 Correct 53 ms 9212 KB Output is correct
16 Correct 51 ms 9284 KB Output is correct
17 Correct 52 ms 9192 KB Output is correct
18 Correct 560 ms 37544 KB Output is correct
19 Correct 18 ms 20564 KB Output is correct
20 Correct 13 ms 1076 KB Output is correct
21 Correct 553 ms 37648 KB Output is correct
22 Correct 631 ms 37760 KB Output is correct
23 Correct 586 ms 37692 KB Output is correct
24 Correct 631 ms 37668 KB Output is correct
25 Correct 546 ms 37580 KB Output is correct
26 Correct 585 ms 37608 KB Output is correct
27 Correct 628 ms 37616 KB Output is correct