Submission #367823

#	Time	Username	Problem	Language	Result	Execution time	Memory
367823		phathnv	Sateliti (COCI20_satellti)	C++11	110 / 110	1936 ms	62252 KiB

Main

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Sateliti"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 2000 + 10;
const int base = 1637;

int m, n, lenS, ind[N * N], tmp[N * N], ord[N][N], pot[N];
char a[N][N], s[N * N];
ll hashed[N * N], pw[N * N];

void readInput(){
    scanf("%d %d", &m, &n);
    for(int i = 1; i <= m; i++)
        scanf("%s", a[i] + 1);
}

ll getHash(int l, int r){
    return hashed[r] - hashed[l - 1] * pw[r - l + 1];
}

int cmp(int x, int y){
    if (getHash(x, x + n - 1) == getHash(y, y + n - 1))
        return 0;
    int l = 1, r = n - 1, len = 0;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (getHash(x, x + mid - 1) == getHash(y, y + mid - 1)){
            len = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    if (s[x + len] > s[y + len])
        return 1;
    return -1;
}

void mySort(int l, int r){
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    mySort(l, mid);
    mySort(mid + 1, r);
    merge(ind + l, ind + mid + 1, ind + mid + 1, ind + r + 1, tmp + l, [&](const int &a, const int &b){
            return (cmp(a, b) == -1);
          });
    for(int i = l; i <= r; i++)
        ind[i] = tmp[i];
}

void prepare(){
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            a[i + m][j] = a[i][j + n] = a[i + m][j + n] = a[i][j];
    int lenS = 0;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= 2 * n; j++)
            s[++lenS] = a[i][j];

    pw[0] = 1;
    for(int i = 1; i <= lenS; i++){
        pw[i] = pw[i - 1] * base;
        hashed[i] = hashed[i - 1] * base + s[i];
    }

    int cnt = 0;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            ind[++cnt] = (i - 1) * (2 * n) + j;
//    sort(ind + 1, ind + 1 + cnt, [&](const int &a, const int &b){
//            return (cmp(a, b) == -1);
//         });
    mySort(1, cnt);

    int cur = 0;
    for(int i = 1; i <= cnt; i++){
        if (i > 1 && cmp(ind[i - 1], ind[i]) == -1)
            cur++;
        int x = ind[i] / (2 * n) + 1;
        int y = (ind[i] - 1) % (2 * n) + 1;
        ord[x][y] = cur;
    }

    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            ord[i + m][j] = ord[i][j + n] = ord[i + m][j + n] = ord[i][j];
}

int findSmallestShift(int col){
    int l = 1, res = -1;
    while (l <= m){
        res = l;
        int cur = l, r = l + 1;
        while (r <= 2 * m && ord[cur][col] <= ord[r][col]){
            if (ord[cur][col] < ord[r][col])
                cur = l;
            else
                cur++;
            r++;
        }
        while (l <= cur)
            l += (r - cur);
    }
    return res;
}

void solve(){
    for(int i = 1; i <= n; i++)
        pot[i] = findSmallestShift(i);
    int best = 1;
    for(int i = 2; i <= n; i++){
        int flag = 0;
        for(int j = 1; j <= m; j++){
            if (ord[pot[best] + j - 1][best] == ord[pot[i] + j - 1][i])
                continue;
            if (ord[pot[best] + j - 1][best] > ord[pot[i] + j - 1][i])
                flag = 1;
            break;
        }
        if (flag)
            best = i;
    }

    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++)
            putchar(a[pot[best] + i - 1][best + j - 1]);
        putchar('\n');
    }
}

int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    readInput();
    prepare();
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void readInput()':
Main.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |     scanf("%d %d", &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |         scanf("%s", a[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  143 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  144 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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