#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
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)) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
