oj.uz

Submission #489266

# Submission time Handle Problem Language Result Execution time Memory
489266 2021-11-21T20:23:02 Z inksamurai Sateliti (COCI20_satellti) C++17
110 / 110
 966 ms 98644 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3HIYw7x ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;

const int _n=1001;

//snuke's modular int
template <ll mod>
struct modint{
  ll x; // typedef long long ll;
  modint(ll x=0):x((x%mod+mod)%mod){}
  modint operator-()const{ return modint(-x);}
  modint& operator+=(const modint a){ if((x+=a.x)>=mod) x-=mod; return *this; }
  modint& operator-=(const modint a){ if((x+=mod-a.x)>=mod) x-=mod; return *this; }
  modint& operator*=(const modint a){ (x*=a.x)%=mod; return *this; }
  modint operator+(const modint a)const{ modint res(*this); return res+=a; }
  modint operator-(const modint a)const{ modint res(*this); return res-=a; }
  modint operator*(const modint a)const{ modint res(*this); return res*=a; }
  modint pow(ll n) const {
    modint res=1,x(*this);
    while(n){
        if(n&1)res*=x;
        x*=x;
        n>>=1;
    }
    return res;
  }
  modint inv() const { return pow(mod-2); }
};
using mint=modint<998244353>;

const mint p=17,q=11;
mint pw[2*_n+10][2*_n+10],invpw[2*_n+10][2*_n+10];
mint dp[2*_n+10][2*_n+10];

void pre_eval(vec(string) a){
	int h=sz(a),w=sz(a[0]);
	pw[0][0]=1;
	rep(i,2*_n){
		rep(j,2*_n){
			if(!i and !j) pw[i][j]=1;
			else if(i==0) pw[i][j]=pw[i][j-1]*q;
			else pw[i][j]=pw[i-1][j]*p;
			invpw[i][j]=pw[i][j].inv();
		}
	}
	rep(i,2*h){
		rep(j,2*w){
			dp[i][j]=mint(a[i%h][j%w])*pw[i][j];
			if(i) dp[i][j]+=dp[i-1][j];
			if(j) dp[i][j]+=dp[i][j-1];
			if(i and j) dp[i][j]-=dp[i-1][j-1];
		}
	}
}

mint rectangle_sum(int sx,int sy,int tx,int ty){
	mint _sum=dp[tx][ty];
	if(sx) _sum-=dp[sx-1][ty];
	if(sy) _sum-=dp[tx][sy-1];
	if(sx and sy) _sum+=dp[sx-1][sy-1];
	_sum*=invpw[sx][sy];
	return _sum;
}

int main(){
_3HIYw7x;
	int h,w;
	cin>>h>>w;
	vec(string) a(h);
	rep(i,h){
		cin>>a[i];
	}
	pre_eval(a);
	pii hm={-1,-1};
	rep(i,h){
		rep(j,w){
			if(hm.fi==-1) hm={i,j};
			else{
				int sx=i,sy=j,tx=i+h-1,ty=j+w-1;
				int _sx=hm.fi,_sy=hm.se,_tx=hm.fi+h-1,_ty=hm.se+w-1;
				// perform binary search on ro-matching
				int l=1,r=h,c=0;
				while(l<=r){
					int m=(l+r)>>1;
					mint _a=rectangle_sum(_sx,_sy,_sx+m-1,_sy+w-1);
					mint _b=rectangle_sum(sx,sy,sx+m-1,sy+w-1);
					if(_a.x==_b.x){
						c=m;
						l=m+1;
					}else{
						r=m-1;
					}
				}
				int ro=c;
				// perform binary search on co-matching
				l=1,r=w,c=0;
				while(l<=r){
					int m=(l+r)>>1;
					mint _a=rectangle_sum(_sx,_sy,_sx+ro,_sy+m-1);
					mint _b=rectangle_sum(sx,sy,sx+ro,sy+m-1);
					if(_a.x==_b.x){
						c=m;
						l=m+1;
					}else{
						r=m-1;
					}
				}
				int co=c;
				if(a[(_sx+ro)%h][(_sy+co)%w]>a[(sx+ro)%h][(sy+co)%w]){
					hm={i,j};
				}
			}
		}
	}
	int x=hm.fi,y=hm.se;
	rep(i,h){
		rep(j,w){
			cout<<a[(x+i)%h][(y+j)%w];
		}
		cout<<"\n";
	}
//	
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:93:19: warning: unused variable 'tx' [-Wunused-variable]
   93 |     int sx=i,sy=j,tx=i+h-1,ty=j+w-1;
      |                   ^~
Main.cpp:93:28: warning: unused variable 'ty' [-Wunused-variable]
   93 |     int sx=i,sy=j,tx=i+h-1,ty=j+w-1;
      |                            ^~
Main.cpp:94:29: warning: unused variable '_tx' [-Wunused-variable]
   94 |     int _sx=hm.fi,_sy=hm.se,_tx=hm.fi+h-1,_ty=hm.se+w-1;
      |                             ^~~
Main.cpp:94:43: warning: unused variable '_ty' [-Wunused-variable]
   94 |     int _sx=hm.fi,_sy=hm.se,_tx=hm.fi+h-1,_ty=hm.se+w-1;
      |                                           ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 95368 KB Output is correct
2 Correct 579 ms 95372 KB Output is correct
3 Correct 577 ms 95368 KB Output is correct
4 Correct 580 ms 95372 KB Output is correct
5 Correct 572 ms 95372 KB Output is correct
6 Correct 579 ms 95308 KB Output is correct
7 Correct 577 ms 95368 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 95368 KB Output is correct
2 Correct 579 ms 95372 KB Output is correct
3 Correct 577 ms 95368 KB Output is correct
4 Correct 580 ms 95372 KB Output is correct
5 Correct 572 ms 95372 KB Output is correct
6 Correct 579 ms 95308 KB Output is correct
7 Correct 577 ms 95368 KB Output is correct
8 Correct 612 ms 95644 KB Output is correct
9 Correct 581 ms 95456 KB Output is correct
10 Correct 581 ms 95408 KB Output is correct
11 Correct 605 ms 95660 KB Output is correct
12 Correct 608 ms 95652 KB Output is correct
13 Correct 619 ms 95664 KB Output is correct
14 Correct 611 ms 95660 KB Output is correct
15 Correct 606 ms 95664 KB Output is correct
16 Correct 609 ms 95688 KB Output is correct
17 Correct 612 ms 95668 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 95368 KB Output is correct
2 Correct 579 ms 95372 KB Output is correct
3 Correct 577 ms 95368 KB Output is correct
4 Correct 580 ms 95372 KB Output is correct
5 Correct 572 ms 95372 KB Output is correct
6 Correct 579 ms 95308 KB Output is correct
7 Correct 577 ms 95368 KB Output is correct
8 Correct 612 ms 95644 KB Output is correct
9 Correct 581 ms 95456 KB Output is correct
10 Correct 581 ms 95408 KB Output is correct
11 Correct 605 ms 95660 KB Output is correct
12 Correct 608 ms 95652 KB Output is correct
13 Correct 619 ms 95664 KB Output is correct
14 Correct 611 ms 95660 KB Output is correct
15 Correct 606 ms 95664 KB Output is correct
16 Correct 609 ms 95688 KB Output is correct
17 Correct 612 ms 95668 KB Output is correct
18 Correct 921 ms 98464 KB Output is correct
19 Correct 583 ms 95440 KB Output is correct
20 Correct 582 ms 95424 KB Output is correct
21 Correct 900 ms 98628 KB Output is correct
22 Correct 956 ms 98564 KB Output is correct
23 Correct 905 ms 98520 KB Output is correct
24 Correct 953 ms 98532 KB Output is correct
25 Correct 899 ms 98500 KB Output is correct
26 Correct 966 ms 98644 KB Output is correct
27 Correct 954 ms 98488 KB Output is correct