oj.uz

답안 #448120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
448120 2021-07-29T02:41:11 Z ignaciocanta Sateliti (COCI20_satellti) C++14
110 / 110
 542 ms 34920 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
//template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
 
using tint = long long;
using ld = long double;
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)	
 
using pi = pair<int,int>;
using pl = pair<tint,tint>;
using vi = vector<int>;
using vl = vector<tint>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vb = vector<bool>;
 
#define pb push_back
#define pf push_front
#define rsz resize
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sz(x) (int)(x).size()
#define ins insert
 
#define f first
#define s second
#define mp make_pair
 
#define DBG(x) cerr << #x << " = " << x << endl;
 
const int MOD = 1e9+7; 
const int mod = 998244353;
const int MX = 1005;
const tint INF = 1e18; 
const int inf = 1e9;
const ld PI = acos(ld(-1)); 
const ld eps = 1e-5;
 
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
 
template<class T> void remDup(vector<T> &v){ 
	sort(all(v)); v.erase(unique(all(v)),end(v));
}
 
template<class T> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; 
} 
template<class T> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; 
}
 
bool valid(int x, int y, int n, int m){
	return (0<=x && x<n && 0<=y && y<m);
}
 
int cdiv(int a, int b) { return a/b+((a^b)>0&&a%b); } //redondea p arriba
int fdiv(int a, int b) { return a/b-((a^b)<0&&a%b); } //redondea p abajo
 
void NACHO(string name = ""){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(sz(name)){
		freopen((name+".in").c_str(), "r", stdin);
		freopen((name+".out").c_str(), "w", stdout);
	}
}

struct mi {
 	int v; explicit operator int() const { return v; } 
	mi() { v = 0; }
	mi(tint _v):v(_v%MOD) { v += (v<0)*MOD; }
};
mi& operator+=(mi& a, mi b) { 
	if ((a.v += b.v) >= MOD) a.v -= MOD; 
	return a; }
mi& operator-=(mi& a, mi b) { 
	if ((a.v -= b.v) < 0) a.v += MOD; 
	return a; }
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((tint)a.v*b.v); }
mi& operator*=(mi& a, mi b) { return a = a*b; }
mi pow(mi a, tint p) { assert(p >= 0); 
	return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
mi inv(mi a) { assert(a.v != 0); return pow(a,MOD-2); }
mi operator/(mi a, mi b) { return a*inv(b); }

char a[MX][MX];
mi hsh[2*MX][2*MX];
mi sh[2*MX][2*MX];
mi pw1[2*MX], pw2[2*MX];

int P1 = 9973, P2 = 10007;

mi query(int a, int b, int c, int d){
	return sh[c][d] - sh[a-1][d] - sh[c][b-1] + sh[a-1][b-1];
}

int main(){
	NACHO();
	// trabajar con los shifts es molesto. Por eso creamos una nueva matriz de tamaño 2*n y 2*m
	// para que un shift corresponda a cualquier submatriz de n*m en esta nueva matriz.
	// como comparamos lexicograficamente dos submatrices?
	// podemos hacerlo con hashing en O(logn).
	int n, m; cin >> n >> m;
	pw1[0] = pw2[0] = 1;
	FOR(i, 1, 2*n+1) pw1[i] = pw1[i-1] * P1;
	FOR(i, 1, 2*m+1) pw2[i] = pw2[i-1] * P2;
	F0R(i, n) cin >> a[i];
	F0R(i, 2*n){
		F0R(j, 2*m){
			hsh[i][j] = a[i%n][j%m] * pw1[i+1] * pw2[j+1];
		}
	}
	FOR(i, 1, 2*n+1){
		FOR(j, 1, 2*m+1){
			sh[i][j] = sh[i-1][j] + sh[i][j-1] - sh[i-1][j-1] + hsh[i-1][j-1];
		}
	}
	int posX = 1, posY = 1;
	FOR(i, 1, n+2){
		FOR(j, 1, m+2){
			int low = -1, high = n;
			while(high-low > 1){
				int mid = low+(high-low)/2;
				mi curHshErase = query(i, j, i+mid, j+m-1) * (pw1[posX] * pw2[posY]);
				mi bestHshErase = query(posX, posY, posX+mid, posY+m-1) * (pw1[i] * pw2[j]);
				if((int)curHshErase == (int)bestHshErase) low = mid;
				else high = mid;
			}
			int X = high;
			low = -1, high = m;
			while(high-low > 1){
				int mid = low+(high-low)/2;
				mi curHshErase = query(i, j, i+X, j+mid) * (pw1[posX] * pw2[posY]);
				mi bestHshErase = query(posX, posY, posX+X, posY+mid) * (pw1[i] * pw2[j]);
				if((int)curHshErase == (int)bestHshErase) low = mid;
				else high = mid;
			}
			int Y = high;
			if(a[(i+X-1)%n][(j+Y-1)%m] < a[(posX+X-1)%n][(posY+Y-1)%m]){
				posX = i, posY = j;
			} 
		}
	}
	FOR(i, posX-1, posX+n-1){
		FOR(j, posY-1, posY+m-1){
			cout << a[i%n][j%m];
		}
		cout << "\n";
	}
}
/*
3 5
..*.*
**..*
****.
*/

Compilation message

Main.cpp: In function 'void NACHO(std::string)':
Main.cpp:74:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   freopen((name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:75:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   freopen((name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31948 KB Output is correct
2 Correct 15 ms 31948 KB Output is correct
3 Correct 15 ms 31936 KB Output is correct
4 Correct 15 ms 31960 KB Output is correct
5 Correct 15 ms 31948 KB Output is correct
6 Correct 15 ms 31948 KB Output is correct
7 Correct 15 ms 31948 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31948 KB Output is correct
2 Correct 15 ms 31948 KB Output is correct
3 Correct 15 ms 31936 KB Output is correct
4 Correct 15 ms 31960 KB Output is correct
5 Correct 15 ms 31948 KB Output is correct
6 Correct 15 ms 31948 KB Output is correct
7 Correct 15 ms 31948 KB Output is correct
8 Correct 52 ms 32224 KB Output is correct
9 Correct 15 ms 31952 KB Output is correct
10 Correct 15 ms 32192 KB Output is correct
11 Correct 50 ms 32240 KB Output is correct
12 Correct 54 ms 32324 KB Output is correct
13 Correct 51 ms 32244 KB Output is correct
14 Correct 54 ms 32244 KB Output is correct
15 Correct 51 ms 32236 KB Output is correct
16 Correct 63 ms 32240 KB Output is correct
17 Correct 54 ms 32236 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31948 KB Output is correct
2 Correct 15 ms 31948 KB Output is correct
3 Correct 15 ms 31936 KB Output is correct
4 Correct 15 ms 31960 KB Output is correct
5 Correct 15 ms 31948 KB Output is correct
6 Correct 15 ms 31948 KB Output is correct
7 Correct 15 ms 31948 KB Output is correct
8 Correct 52 ms 32224 KB Output is correct
9 Correct 15 ms 31952 KB Output is correct
10 Correct 15 ms 32192 KB Output is correct
11 Correct 50 ms 32240 KB Output is correct
12 Correct 54 ms 32324 KB Output is correct
13 Correct 51 ms 32244 KB Output is correct
14 Correct 54 ms 32244 KB Output is correct
15 Correct 51 ms 32236 KB Output is correct
16 Correct 63 ms 32240 KB Output is correct
17 Correct 54 ms 32236 KB Output is correct
18 Correct 469 ms 33816 KB Output is correct
19 Correct 18 ms 32864 KB Output is correct
20 Correct 21 ms 31976 KB Output is correct
21 Correct 441 ms 34884 KB Output is correct
22 Correct 508 ms 34796 KB Output is correct
23 Correct 444 ms 34808 KB Output is correct
24 Correct 516 ms 34884 KB Output is correct
25 Correct 436 ms 34920 KB Output is correct
26 Correct 512 ms 34800 KB Output is correct
27 Correct 542 ms 34808 KB Output is correct