Submission #489266

#	Time	Username	Problem	Language	Result	Execution time	Memory
489266		inksamurai	Sateliti (COCI20_satellti)	C++17	110 / 110	966 ms	98644 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60