oj.uz

Submission #474116

# Submission time Handle Problem Language Result Execution time Memory
474116 2021-09-17T00:17:32 Z CaroLinda Sateliti (COCI20_satellti) C++14
110 / 110
 2548 ms 66284 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 3 ms 1612 KB Output is correct
3 Correct 3 ms 1612 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1740 KB Output is correct
6 Correct 3 ms 1852 KB Output is correct
7 Correct 3 ms 1720 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 3 ms 1612 KB Output is correct
3 Correct 3 ms 1612 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1740 KB Output is correct
6 Correct 3 ms 1852 KB Output is correct
7 Correct 3 ms 1720 KB Output is correct
8 Correct 131 ms 13908 KB Output is correct
9 Correct 4 ms 844 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 135 ms 13236 KB Output is correct
12 Correct 127 ms 13716 KB Output is correct
13 Correct 139 ms 13744 KB Output is correct
14 Correct 142 ms 13724 KB Output is correct
15 Correct 135 ms 13880 KB Output is correct
16 Correct 140 ms 14000 KB Output is correct
17 Correct 141 ms 13752 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1740 KB Output is correct
2 Correct 3 ms 1612 KB Output is correct
3 Correct 3 ms 1612 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1740 KB Output is correct
6 Correct 3 ms 1852 KB Output is correct
7 Correct 3 ms 1720 KB Output is correct
8 Correct 131 ms 13908 KB Output is correct
9 Correct 4 ms 844 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 135 ms 13236 KB Output is correct
12 Correct 127 ms 13716 KB Output is correct
13 Correct 139 ms 13744 KB Output is correct
14 Correct 142 ms 13724 KB Output is correct
15 Correct 135 ms 13880 KB Output is correct
16 Correct 140 ms 14000 KB Output is correct
17 Correct 141 ms 13752 KB Output is correct
18 Correct 2529 ms 66284 KB Output is correct
19 Correct 19 ms 21196 KB Output is correct
20 Correct 26 ms 1736 KB Output is correct
21 Correct 2216 ms 58864 KB Output is correct
22 Correct 2215 ms 58696 KB Output is correct
23 Correct 2264 ms 58628 KB Output is correct
24 Correct 2294 ms 58680 KB Output is correct
25 Correct 2238 ms 60260 KB Output is correct
26 Correct 2260 ms 60316 KB Output is correct
27 Correct 2548 ms 58540 KB Output is correct