Submission #1276262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276262		codefox	Sateliti (COCI20_satellti)	C++20	0 / 110	1 ms	568 KiB

Main

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;
    
#define int long long
#define pii pair<int, int>

const int mod = 1e9+7;

const int N = 10;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; i++) cin >> grid[i];

    int order[n][m] = {0};
    pii sorted[n*m];
    int cum[n*m] = {0};

    int k = 0;
    for (int i = 0 ;i < n; i++)
    {
        for (int j = 0; j < m; j++) 
            if (grid[i][j]=='*') 
            {
                sorted[k] = {i, j};
                order[i][j] = 0;
                cum[1]++;
                k++;
            }
    }
    for (int i = 0 ;i < n; i++)
    {
        for (int j = 0; j < m; j++) 
            if (grid[i][j]=='.') 
            {
                sorted[k] = {i, j};
                order[i][j] = 1;
                k++;
            }
    }

    for (int i = 0; i < N; i++)
    {
        pii nsorted[n*m];
        for (auto ele:sorted)
        {
            auto [a, b] = ele;
            int o = order[a][((b-(1<<i))%m+m)%m];
            nsorted[cum[o]] = {a, ((b-(1<<i))%m+m)%m}; 
            cum[o]++;
        }  
        int norder[n][m];
        int t = -1;
        pii last = {-1, -1};
        for (int j = 0; j < n*m; j++)
        {
            auto [a, b] = nsorted[j];
            int o1 = order[a][b];
            int o2 = order[a][((b-(1<<i))%m+m)%m];
            if (make_pair(o1, o2)!=last) t++;
            last = {o1, o2};
            norder[a][b] = t;
            cum[j] = 0;
        }
        for (int j = 0; j < n*m; j++)
        {
            auto [a, b] = nsorted[j];
            order[a][b] = norder[a][b];
            if (order[a][b]==n*m-1) break;
            cum[order[a][b]+1]++;
        }
        for (int j = 1; j < n*m; j++)
        {
            cum[j] += cum[j-1];
        }
    }

    
    for (int i = 0; i < N; i++)
    {
        pii nsorted[n*m];
        for (auto ele:sorted)
        {
            auto [a, b] = ele;
            int o = order[((a-(1<<i))%n+n)%n][b];
            nsorted[cum[o]] = {((a-(1<<i))%n+n)%n,b}; 
            cum[o]++;
        }  
        int norder[n][m];
        int t = -1;
        pii last = {-1, -1};
        for (int j = 0; j < n*m; j++)
        {
            auto [a, b] = nsorted[j];
            int o1 = order[a][b];
            int o2 = order[((a-(1<<i))%n+n)%n][b];
            if (make_pair(o1, o2)!=last) t++;
            last = {o1, o2};
            norder[a][b] = t;
            cum[j] = 0;
        }
        for (int j = 0; j < n*m; j++)
        {
            sorted[j] = nsorted[j];
            auto [a, b] = nsorted[j];
            order[a][b] = norder[a][b];
            if (order[a][b]==n*m-1) break;
            cum[order[a][b]+1]++;
        }
        for (int j = 1; j < n*m; j++)
        {
            cum[j] += cum[j-1];
        }
    }

    auto [a, b] = sorted[0];

    for (int i = a; i < n+a; i++)
    {
        cout << grid[i%n].substr(b, m-b) << grid[i%n].substr(0, b) << "\n";
    }

    return 0;
}

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