제출 #625025

#제출 시각아이디문제언어결과실행 시간메모리
625025Soul234Sateliti (COCI20_satellti)C++14
110 / 110
526 ms35080 KiB
#include<bits/stdc++.h> using namespace std; #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 rep(i,a,b) FOR(i,a,b) #define REP(a) F0R(_,a) #define each(e,a) for(auto &e : (a)) #define sz(v) (int)(v).size() #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define rsz resize #define pb push_back #define f first #define s second #define pf push_front #define ft front() #define bk back() #define eb emplace_back #define lb lower_bound #define ub upper_bound #define tcT template<class T #define tcTU tcT, class U #define nl "\n" using ll = long long; using vi = vector<int>; using vl = vector<ll>; using vb = vector<bool>; using pi = pair<int,int>; using vpi = vector<pi>; using str = string; using vs = vector<str>; using db = long double; using pl = pair<ll,ll>; using pd = pair<db,db>; tcT> using V = vector<T>; tcT> using pqg = priority_queue<T,vector<T>,greater<T>>; tcTU> using PR = pair<T,U>; tcT, int SZ> using AR = array<T, SZ>; const int MOD = 1e9+7; const ll INF = 1e18; const int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1}; constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); } constexpr bool onbit(int msk, int i) { return msk>>i&1; } constexpr ll p2(int x) { return 1LL<<x; } constexpr int pct(int x) { return __builtin_popcount(x); } constexpr int lg2(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }; //int only tcT> bool ckmin(T&a, const T&b) { return b < a ? a = b,1 : 0; } tcT> bool ckmax(T&a, const T&b) { return b > a ? a = b,1 : 0; } ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } tcTU> T fstTrue(T lo, T hi, U f) { hi++; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; } tcTU> T lstTrue(T lo, T hi, U f) { lo--; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; } tcT> void remDup(V<T> &v) { sort(all(v)); v.erase(unique(all(v)), end(v)); } void DBG() { cerr << "]\n"; } template<class H, class... T> void DBG(H h, T... t) { cerr << h; if(sizeof...(t)) cerr << ", "; DBG(t...); } #ifdef LOCAL #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) #else #define dbg(...) 0 #endif // LOCAL void setPrec() { cout << fixed << setprecision(16); } void setIO(string NAME = "") { cin.tie(0)->sync_with_stdio(0); setPrec(); if(sz(NAME)) { freopen((NAME + ".inp").c_str(),"r",stdin); freopen((NAME + ".out").c_str(),"w",stdout); } } const int MX = 1e3+10; int N, M; const int P = 2, Q = 3; int PQpow[2*MX][2*MX]; int hs[2*MX][2*MX]; int add(int a, int b) { if((a += b) >= MOD) a-=MOD; return a; } int sub(int a, int b) { return add(a, MOD-b); } int mul(int a, int b) { return 1LL*a*b%MOD; } int getHash(int x, int y, int dx, int dy) { return add(sub(hs[x+dx][y+dy], add(hs[x+dx][y], hs[x][y+dy])), hs[x][y]); } int eq(int x1, int y1, int x2, int y2, int dx, int dy) { return mul(getHash(x1, y1, dx, dy), PQpow[x2][y2]) == mul(getHash(x2, y2, dx, dy), PQpow[x1][y1]); } str S[MX]; void solve() { cin>>N>>M; F0R(i,N) cin>>S[i]; F0R(i,2*N) F0R(j,2*M) { if(i == 0 && j == 0) PQpow[i][j] = 1; else if(j == 0) PQpow[i][j] = mul(PQpow[i-1][j],P); else PQpow[i][j] = mul(PQpow[i][j-1], Q); } F0R(i,2*N) F0R(j,2*M) { hs[i+1][j+1] = mul(S[i%N][j%M] == '.', PQpow[i][j]); hs[i+1][j+1] = sub(add(hs[i+1][j+1], add(hs[i][j+1], hs[i+1][j])), hs[i][j]); } int ansx, ansy; ansx = ansy = 0; F0R(i,N) F0R(j,M) { int lo = 0, hi = N; while(lo<hi) { int mid = lo + (hi-lo+1)/2; if(eq(ansx, ansy, i, j, mid, M)) lo = mid; else hi = mid-1; } int dx, dy; dx = lo; lo = 0, hi = M; while(lo<hi) { int mid = lo + (hi-lo+1)/2; if(eq(ansx+dx, ansy, i+dx, j, 1, mid)) lo = mid; else hi = mid-1; } dy = lo; if(S[(i+dx)%N][(j+dy)%M] < S[(ansx+dx)%N][(ansy+dy)%M]) { ansx = i, ansy = j; } } F0R(i,N) F0R(j,M) { cout << S[(ansx+i)%N][(ansy+j)%M]; if(j == M-1) cout << "\n"; } } int main() { setIO(); int t=1; //cin>>t; while(t-->0) { solve(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     freopen((NAME + ".inp").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     freopen((NAME + ".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...