oj.uz

Submission #625025

# Submission time Handle Problem Language Result Execution time Memory
625025 2022-08-09T09:09:29 Z Soul234 Sateliti (COCI20_satellti) C++14
110 / 110
 526 ms 35080 KB 
#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;
}

Compilation message

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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1264 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 36 ms 8012 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 36 ms 7936 KB Output is correct
12 Correct 48 ms 8072 KB Output is correct
13 Correct 37 ms 8188 KB Output is correct
14 Correct 39 ms 8160 KB Output is correct
15 Correct 36 ms 8184 KB Output is correct
16 Correct 44 ms 8176 KB Output is correct
17 Correct 42 ms 8184 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1264 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 36 ms 8012 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 36 ms 7936 KB Output is correct
12 Correct 48 ms 8072 KB Output is correct
13 Correct 37 ms 8188 KB Output is correct
14 Correct 39 ms 8160 KB Output is correct
15 Correct 36 ms 8184 KB Output is correct
16 Correct 44 ms 8176 KB Output is correct
17 Correct 42 ms 8184 KB Output is correct
18 Correct 424 ms 34964 KB Output is correct
19 Correct 11 ms 16724 KB Output is correct
20 Correct 9 ms 1012 KB Output is correct
21 Correct 421 ms 35080 KB Output is correct
22 Correct 504 ms 35020 KB Output is correct
23 Correct 409 ms 34972 KB Output is correct
24 Correct 483 ms 34916 KB Output is correct
25 Correct 422 ms 34916 KB Output is correct
26 Correct 526 ms 35008 KB Output is correct
27 Correct 506 ms 34856 KB Output is correct