oj.uz

답안 #448109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
448109 2021-07-29T02:29:30 Z ignaciocanta Sateliti (COCI20_satellti) C++14
50 / 110
 3000 ms 36828 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[2*MX][2*MX];
mi hsh[2*MX][2*MX];
mi sh[2*MX][2*MX];
mi pw1[2*MX], pw2[2*MX];

mi 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, n){
		F0R(j, m){
			a[i+n][j] = a[i][j];
			a[i][j+m] = a[i][j];
			a[i+n][j+m] = a[i][j];
		}
	}
	F0R(i, 2*n){
		F0R(j, 2*m){
			hsh[i][j] = a[i][j] * 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) * inv(pw1[i] * pw2[j]);
				mi bestHshErase = query(posX, posY, posX+mid, posY+m-1) * inv(pw1[posX] * pw2[posY]);
				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) * inv(pw1[i] * pw2[j]);
				mi bestHshErase = query(posX, posY, posX+X, posY+mid) * inv(pw1[posX] * pw2[posY]);
				if((int)curHshErase == (int)bestHshErase) low = mid;
				else high = mid;
			}
			int Y = high;
			if(a[i+X-1][j+Y-1] < a[posX+X-1][posY+Y-1]){
				posX = i, posY = j;
			} 
		}
	}
	FOR(i, posX-1, posX+n-1){
		FOR(j, posY-1, posY+m-1){
			cout << a[i][j];
		}
		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 34 ms 32076 KB Output is correct
2 Correct 33 ms 32076 KB Output is correct
3 Correct 33 ms 32144 KB Output is correct
4 Correct 34 ms 32076 KB Output is correct
5 Correct 31 ms 32092 KB Output is correct
6 Correct 31 ms 32076 KB Output is correct
7 Correct 35 ms 32092 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 32076 KB Output is correct
2 Correct 33 ms 32076 KB Output is correct
3 Correct 33 ms 32144 KB Output is correct
4 Correct 34 ms 32076 KB Output is correct
5 Correct 31 ms 32092 KB Output is correct
6 Correct 31 ms 32076 KB Output is correct
7 Correct 35 ms 32092 KB Output is correct
8 Correct 1049 ms 33164 KB Output is correct
9 Correct 41 ms 31948 KB Output is correct
10 Correct 19 ms 33112 KB Output is correct
11 Correct 1035 ms 33164 KB Output is correct
12 Correct 1080 ms 33220 KB Output is correct
13 Correct 1085 ms 33228 KB Output is correct
14 Correct 1120 ms 33308 KB Output is correct
15 Correct 1078 ms 33228 KB Output is correct
16 Correct 1103 ms 33228 KB Output is correct
17 Correct 1122 ms 33220 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 32076 KB Output is correct
2 Correct 33 ms 32076 KB Output is correct
3 Correct 33 ms 32144 KB Output is correct
4 Correct 34 ms 32076 KB Output is correct
5 Correct 31 ms 32092 KB Output is correct
6 Correct 31 ms 32076 KB Output is correct
7 Correct 35 ms 32092 KB Output is correct
8 Correct 1049 ms 33164 KB Output is correct
9 Correct 41 ms 31948 KB Output is correct
10 Correct 19 ms 33112 KB Output is correct
11 Correct 1035 ms 33164 KB Output is correct
12 Correct 1080 ms 33220 KB Output is correct
13 Correct 1085 ms 33228 KB Output is correct
14 Correct 1120 ms 33308 KB Output is correct
15 Correct 1078 ms 33228 KB Output is correct
16 Correct 1103 ms 33228 KB Output is correct
17 Correct 1122 ms 33220 KB Output is correct
18 Execution timed out 3073 ms 36828 KB Time limit exceeded
19 Halted 0 ms 0 KB -