Submission #474116

#	Time	Username	Problem	Language	Result	Execution time	Memory
474116		CaroLinda	Sateliti (COCI20_satellti)	C++14	110 / 110	2548 ms	66284 KiB

Main

#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()
 
const int MAXN = 1010 ;
const int LOG = 20 ;
 
using namespace std ;

int N , M , P ;
int val[50] , valor[MAXN] ;
int tab[LOG+5][MAXN][MAXN]; 
int aux[MAXN][MAXN] ;
vector< pair<int,int> > v ;
char grid[MAXN][MAXN] ;
pair<int,int> amostra[MAXN*MAXN] ;

void constructTab()
{
	for(int i = 0 ; i < N ; i++ )
		for(int j = 0 ; j < M ; j++ )
			tab[0][i][j] = val[grid[i][j]] ;
						
	for(int i = 1 ; (1<<i) <= M ; i++ )
	{
		
		
		P = i ;
		
		sort( all(v) , [&](pair<int,int> p1, pair<int,int> p2)
		{
			if( tab[i-1][p1.first][p1.second] != tab[i-1][p2.first][p2.second] )	
				return tab[i-1][p1.first][p1.second] < tab[i-1][p2.first][p2.second] ;
				
			int idx1 = p1.second+(1<<(i-1)) ;
			if(idx1 >= M ) idx1 -= M ;
			
			int idx2 = p2.second+(1<<(i-1)) ;
			if(idx2 >= M ) idx2 -= M ;
			
			return tab[i-1][p1.first][idx1] < tab[i-1][p2.first][idx2] ;
		}
		) ;
		
		tab[i][ v[0].first ][ v[0].second ] = 0 ;
		for(int j = 1 ; j < sz(v) ; j++ )
		{
			int a = v[j].first, b = v[j].second , s = b ;
			int x = v[j-1].first , y = v[j-1].second ;
			
			if(tab[i-1][a][b] > tab[i-1][x][y])
			{
				tab[i][a][b] = tab[i][x][y]+1 ;
				continue ;
			}
			
			tab[i][a][b] = tab[i][x][y]; 
			
			b += (1<<(i-1)) ;
			if(b >= M) b -= M ;
			
			y += (1<<(i-1)) ;
			if(y >= M ) y -= M ;
			
			if( tab[i-1][a][b] > tab[i-1][x][y] ) tab[i][a][s]++ ;
		}
	}
	
	int cur = (1<<P) ;
	for(int pot = P-1 , K = M-(1<<P) ; pot >= 0 ; pot-- )
	{
		if( K < (1<<pot) ) continue ;
		K -= (1<<pot) ;
		
		sort( all(v) , [&](pair<int,int> p1, pair<int,int> p2)
		{
			if( tab[P][p1.first][p1.second] != tab[P][p2.first][p2.second] )	
				return tab[P][p1.first][p1.second] < tab[P][p2.first][p2.second] ;
				
			int idx1 = p1.second+cur ;
			if(idx1 >= M ) idx1 -= M ;
			
			int idx2 = p2.second+cur ;
			if(idx2 >= M ) idx2 -= M ;
			
			return tab[pot][p1.first][idx1] < tab[pot][p2.first][idx2] ;
		}
		) ;
		
		aux[ v[0].first ][ v[0].second ] = 0 ;
		for(int j = 1 ; j < sz(v) ; j++ )
		{
			int a = v[j].first, b = v[j].second , s = b ;
			int x = v[j-1].first , y = v[j-1].second ;
			
			if(tab[P][a][b] > tab[P][x][y])
			{
				aux[a][b] = aux[x][y]+1 ;
				continue ;
			}
			
			aux[a][b] = aux[x][y] ;
			
			b += cur ;
			if(b >= M) b -= M ;
			
			y += cur ;
			if(y >= M ) y -= M ;
			
			if( tab[pot][a][b] > tab[pot][x][y] ) aux[a][s]++ ;
		}
		
		for(int a = 0 ; a < N ; a++ )
			for(int b = 0 ; b < M ; b++ ) tab[P][a][b] = aux[a][b] ;
			
		cur += (1<<pot) ;
	} 
	
	for(int i = 0 ; i < N ; i++ )
		for(int j = 0 ; j < M ; j++ ) amostra[ tab[P][i][j] ] = make_pair(i,j) ;
	
}

vector<int> vv ;
int aux_valor[MAXN] ;
set< vector<int> > s ;
int suffixArray()
{
	int last = min_element(valor, valor+N)-valor ;
	
	for(int i = 1 ; (1<<(i-1)) < N ; i++ )
	{
		sort(all(vv), [&](int x, int y)
		{
			if( valor[x] != valor[y] ) return valor[x] < valor[y] ;
			int xx = x + (1<<(i-1)) ;
			int yy = y+(1<<(i-1)) ;
			
			if(xx >= N ) xx -= N ;
			if(yy >= N ) yy -= N ;
			
			return valor[xx] < valor[yy] ;
		}
		) ;
		aux_valor[ vv[0] ] = 0 ;
		last = vv[0] ;
		for(int j = 1 ; j < N ; j++ )
		{
			if( valor[vv[j]] != valor[vv[j-1]] ) 
			{
				aux_valor[vv[j]] = aux_valor[vv[j-1]]+1 ;
				continue ;
			}
			
			int x = vv[j]+(1<<(i-1)) ;
			int y = vv[j-1]+(1<<(i-1)) ;
			
			if(x >= N ) x -= N ;
			if(y >= N) y -= N ;
			
			if(valor[x] != valor[y]) aux_valor[vv[j]] = aux_valor[vv[j-1]]+1 ;
			else aux_valor[vv[j]] = aux_valor[vv[j-1]] ;
		}
		
		for(int j = 0 ; j < N ; j++ ) valor[j] = aux_valor[j] ;
	}

	return last ;
}

int main()
{
	val[42] = 0 ;
	val[46] = 1 ;
	
	scanf("%d %d", &N, &M ) ;
	for(int i = 0 ; i < N ;i++ )
		for(int j = 0 ; j < M ; j++ )
			scanf(" %c", &grid[i][j] ) ,v.push_back(make_pair(i,j)) ;
						
	constructTab() ;
	
	for(int i=  0 ; i < N ; i++ ) vv.push_back(i) ;
	
	for(int j = 0 ; j < M ; j++ )
	{
		for(int g = 0 ; g < N ; g++ ) valor[g] = tab[P][g][j] ;
		int guy = suffixArray() ;
		for(int g = 0 ; g < N ; g++ ) valor[g] = tab[P][g][j] ;
		
		vector<int> ans = {valor[guy]} ;
		for(int i = guy+1 ; i != guy ; i++ )
		{
			if(i >= N )
			{
				i = -1 ;
				continue ;
			}
			ans.push_back(valor[i]) ;
		}
		s.insert(ans) ;
	}
	
	
	vector<int> winner = *s.begin() ;
	for(auto e : winner )
	{
		int x = amostra[e].first ;
		int y= amostra[e].second ;
		
		printf("%c", grid[x][y] ) ;
		for(int i = y+1 ; i != y ; i++ )
		{
			if(i >= M)
			{
				i = -1 ;
				continue ;
			}
			printf("%c",grid[x][i]) ;
		}
		printf("\n") ;
	}
	
}

Compilation message (stderr)

Main.cpp: In function 'void constructTab()':
Main.cpp:32:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |    tab[0][i][j] = val[grid[i][j]] ;
      |                       ~~~~~~~~~^
Main.cpp: In function 'int main()':
Main.cpp:186:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |  scanf("%d %d", &N, &M ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:189:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |    scanf(" %c", &grid[i][j] ) ,v.push_back(make_pair(i,j)) ;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~

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