Submission #1206515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206515		_rain_	Sateliti (COCI20_satellti)	C++20	0 / 110	11 ms	16528 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)2000;
	char c[N+2][N+2];
	int p[N+2][N+2]={};
	int ID[N+2][N+2]={};
	
	int numrow,numcol;
	int length,need_row;
	vector<pair<int,int>>v;
	

	void build_board(){
		for(int i=1;i<=numrow;++i){
			for(int j=numcol+1;j<=2*numcol;++j) {
				c[i][j]=c[i][j-numcol];
			}
		}
		for(int i=numrow+1;i<=2*numrow;++i){
			for(int j=1;j<=numcol;++j) {
				c[i][j]=c[i-numrow][j];
			}
		}
		for(int i=numrow+1;i<=2*numrow;++i){
			for(int j=numcol+1;j<=2*numcol;++j){
				c[i][j]=c[i-numrow][j-numcol];
			}
		}
		return;
	}
	
	class Hash_table{
		public:
			vector<int>h,p;
			const int MOD=1e9+9;
			const int base=9973;
			void init(int _n){
				h.assign(_n+2,0);
				p.assign(_n+2,0);
			}
			void hash(int id){
				p[0]=1;
				for(int i=1;i<=numcol;++i){
					p[i]=(LL)p[i-1]*base%MOD;
				}
				for(int i=1;i<=numcol;++i){
					h[i]=((LL)h[i-1]*base+c[id][i]-'a'+1)%MOD;
				}
			}
			int Get(int l,int r){
				return ((LL)h[r]-(LL)h[l-1]*p[r-l+1]+(LL)MOD*MOD)%MOD;
			}
	};
	Hash_table h[N+2];

	//... COMPARE THE FUNCTION
		bool cmp(pair<int,int>&x,pair<int,int>&y){
			
			int low=1,high=length,p=0;
			while (low<=high){
				int mid=(low+high)/2;
				if (h[x.first].Get(x.second,x.second+mid-1)==h[y.first].Get(y.second,y.second+mid-1)){
					p=mid;
					low=mid+1;
				}
				else high=mid-1;
			}

			
			if (p!=length) return c[x.first][x.second+p]<c[y.first][y.second+p];
			if (x.first!=y.first) return x.first<y.first;
			return x.second<y.second;
		}
		
		bool equal(pair<int,int>&x,pair<int,int>&y){
			int low=1,high=length,p=0;
			while (low<=high){
				int mid=(low+high)/2;
				if (h[x.first].Get(x.second,x.second+length-1)==h[y.first].Get(y.second,y.second+length-1)){
					p=mid;
					low=mid+1;
				}
				else high=mid-1;
			}
			return p==length;
		}

	bool check_possible(pair<int,int>&point,int x){
		return point.first+(need_row-x)<=numrow;
	}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define task "main"
	if (fopen(task".inp","r")){
		freopen(task".inp","r",stdin);
		freopen(task".out","w",stdout);
	}
	
	cin>>numrow>>numcol;
	for(int i=1;i<=numrow;++i){
		for(int j=1;j<=numcol;++j){
			cin>>c[i][j];
		}
	}
	build_board();
	numrow=2*numrow;
	numcol=2*numcol;
	length=numcol/2;
	need_row=numrow/2;

	for(int i=1;i<=numrow;++i) {
		h[i].init(numcol);
		h[i].hash(i);
		for(int j=1;j<=numcol/2;++j) v.push_back({i,j});
	};
	sort(v.begin(),v.end(),cmp);
	memset(p,0x3f,sizeof p);
	int available=1;
	int cnt=0;
	vector<pair<int,int>>q;
	for(int i=0,j=0;i<v.size();++i){
		if (available==false) break;
		while (j<v.size() && equal(v[i],v[j])) ++j;
		bool ok=available;
		++cnt;
		for(int id=i;id<j;++id){
			int x=v[id].first,y=v[id].second;
			ID[x][y]=cnt;
			if (check_possible(v[id],available) && available) q.push_back(v[id]),ok=false;
		}
		available=ok;
		i=j-1;
	}
	pair<int,int>final={-1,-1};
	for(int i=1;i<=need_row;++i){
		vector<pair<int,int>>used;
		bool ok=false;
		for(auto&x:q) {
			p[x.first][x.second]=i;
			if (i==need_row){
				final=x;
				ok=true;
			}
			used.push_back({x.first+1,x.second});
		}
		if (ok) break;
		sort(used.begin(),used.end(),[&](pair<int,int> x,pair<int,int> y){
			return ID[x.first][x.second]<ID[y.first][y.second];
		});
		while (used.size()>1 && ID[used.back().first][used.back().second]!=ID[used.front().first][used.front().second]){
			used.pop_back();
		}
		swap(q,used);
	}
	
	for(int i=1;i<=numrow;++i){
		for(int j=1;j<=numcol;++j) if (p[i][j]==need_row) final={i,j};
	}
	assert(final.first!=-1 && final.second!=-1);
	for(int i=final.first-need_row+1;i<=final.first;++i){
		for(int j=final.second;j<=final.second+length-1;++j) cout<<c[i][j];
		cout<<'\n';
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:99:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |                 freopen(task".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:100:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |                 freopen(task".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 60