Submission #474114

#	Time	Username	Problem	Language	Result	Execution time	Memory
474114		CaroLinda	Sateliti (COCI20_satellti)	C++14	0 / 110	3 ms	1716 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 ;
int val[50] ;
int tab[LOG+5][MAXN][MAXN]; 
int aux[MAXN][MAXN] ;
vector< pair<int,int> > v ;
char grid[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]] ;
			
	int P = 0 ;
			
	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++, cout << endl )
		for(int j = 0 ; j < M ; j++ ) cout << tab[P][i][j] << " " ;
	
}

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() ;
}

Compilation message (stderr)

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

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