oj.uz

Submission #395534

# Submission time Handle Problem Language Result Execution time Memory
395534 2021-04-28T12:57:30 Z MrRobot_28 Sateliti (COCI20_satellti) C++17
110 / 110
 2041 ms 32452 KB 
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sz(a) (int)a.size()
#define ll long long
#define ld long double
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const int N = 1e3 + 100;
int A[N][N];
vector <pair <int, int> > mass;
pair <int, int> hashes1[N][N];
pair <int, int> hashes2[N][N];
pair <int, int> hashes3[N][N];
int Pow1[N], Pow2[N];
int n, m;
bool cmp1(int a, int b)
{
    for(int j = 0; j < m; j++)
    {
        if(A[a][j] != A[b][j])
        {
            return A[a][j] < A[b][j];
        }
    }
    return 0;
}
bool cmp(pair <int, int>  a, pair <int, int>  b)
{
    int i1 = a.X;
    int j1 = a.Y;
    int i2 = b.X;
    int j2 = b.Y;
    for(int i = 0; i < n;i++)
    {
        if(hashes3[(i1 + i) % n][j1] != hashes3[(i2 + i) % n][j2])
        {
            for(int j = 0; j < m; j++)
            {
                int k1 = A[(i1 + i) % n][(j1 + j) % m];
                int k2 = A[(i2 + i) % n][(j2 + j) % m];
                if(k1 != k2)
                {
                    return k1 < k2;
                }
            }
        }
    }
    return 0;
}
signed main()
{
    //ifstream cin("286.txt");
//    ios_base::sync_with_stdio(0);
  //  cin.tie(0);
    //cout.tie(0);
    cin >> n >> m;
    Pow1[0] = Pow2[0] = 1;
    for(int i = 1; i < N; i++)
    {
        Pow1[i] = Pow1[i - 1] * 2 % mod1;
        Pow2[i] = Pow2[i - 1] * 2 % mod2;
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            char t;
            cin >> t;
            if(t == '*')
            {
                A[i][j] = 0;
            }
            else
            {
                A[i][j] = 1;
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            hashes1[i][j].X = hashes1[i][j].Y = A[i][j];
            if(j != 0)
            {
                hashes1[i][j].X = (hashes1[i][j].X + hashes1[i][j - 1].X * 2) % mod1;
                hashes1[i][j].Y = (hashes1[i][j].Y + hashes1[i][j - 1].Y * 2) % mod2;
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = m - 1; j >= 0; j--)
        {
            hashes2[i][j].X = hashes2[i][j].Y = A[i][j] * Pow1[m - j - 1];
            if(j != m - 1)
            {
                hashes2[i][j].X = (hashes2[i][j].X + hashes2[i][j + 1].X) % mod1;
                hashes2[i][j].Y = (hashes2[i][j].Y + hashes2[i][j + 1].Y) % mod2;
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(j == 0)
            {
                hashes3[i][j] = hashes2[i][j];
            }
            else
            {
                hashes3[i][j].X = (hashes1[i][j - 1].X + 1LL * hashes2[i][j].X * Pow1[j]) % mod1;
                hashes3[i][j].Y = (hashes1[i][j - 1].Y + 1LL * hashes2[i][j].Y * Pow2[j]) % mod2;
            }
        }
    }
  //  cout << "A\n";
    vector <int> sorted, sorted1, sorted2;
    vector <int> st1(n), col(n);
    vector <int> cnt(n);
    vector <int> start(n);
    vector <int> col1(n);
    for(int i = 0; i < n; i++)
    {
        sorted.push_back(i);
    }
    sort(sorted.begin(), sorted.end(), cmp1);
    for(int t = m - 1; t >= 0; t--)
    {
        for(auto i : sorted)
        {
            if(A[i][t] == 0)
            {
                sorted1.push_back(i);
            }
            else
            {
                sorted2.push_back(i);
            }
        }
        sorted.clear();
        for(auto i : sorted1)
        {
            sorted.push_back(i);
        }
        for(auto i : sorted2)
        {
            sorted.push_back(i);
        }
        int cl = 0;
        col[sorted[0]] = 0;
        for(int i = 1; i < n; i++)
        {
            if(hashes3[sorted[i]][t] != hashes3[sorted[i - 1]][t])
            {
                cl++;
            }
            col[sorted[i]] = cl;
        }
        sorted2 = sorted;
        int k = 0;
        while((1 << k) <= n)
        {
            for(int i = 0; i < n; i++)
            {
                cnt[i] = start[i] = 0;
            }
            for(int i = 0; i < n; i++)
            {
                cnt[col[i]]++;
            }
            for(int i=  1; i < n; i++)
            {
                start[i] = start[i - 1] + cnt[i - 1];
            }
            for(auto i : sorted)
            {
                int of = (i - (1 << k) + n) % n;
                st1[start[col[of]]++] = of;
            }
            int cl = 0;
            for(int i = 0; i < n; i++)
            {
                sorted[i] = st1[i];
                if(i != 0)
                {
                    int a = sorted[i - 1];
                    int b = sorted[i];
                    if(col[a] != col[b] || col[(a + (1 << k) + n) % n] != col[(b + (1 << k) + n) % n])
                    {
                        cl++;
                    }
                }
                col1[sorted[i]] = cl;
            }
            for(int i = 0; i < n; i++)
            {
                col[i] = col1[i];
            }
            k++;
        }
       // cout << sorted[0] << " " << t << "\n";
        mass.push_back({sorted[0], t});
        sorted = sorted2;
        sorted1.clear();
        sorted2.clear();
    }
    sort(mass.begin(), mass.end(), cmp);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            int k = A[(i + mass[0].X) % n][(j + mass[0].Y) % m];
            if(k == 0)
            {
                cout << "*";
            }
            else
            {
                cout << ".";
            }
        }
        cout << "\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1000 KB Output is correct
3 Correct 2 ms 1100 KB Output is correct
4 Correct 2 ms 1024 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1080 KB Output is correct
7 Correct 4 ms 1100 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1000 KB Output is correct
3 Correct 2 ms 1100 KB Output is correct
4 Correct 2 ms 1024 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1080 KB Output is correct
7 Correct 4 ms 1100 KB Output is correct
8 Correct 37 ms 7240 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 5052 KB Output is correct
11 Correct 79 ms 7156 KB Output is correct
12 Correct 58 ms 7364 KB Output is correct
13 Correct 54 ms 7404 KB Output is correct
14 Correct 44 ms 7392 KB Output is correct
15 Correct 42 ms 7400 KB Output is correct
16 Correct 43 ms 7372 KB Output is correct
17 Correct 60 ms 7408 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1000 KB Output is correct
3 Correct 2 ms 1100 KB Output is correct
4 Correct 2 ms 1024 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1080 KB Output is correct
7 Correct 4 ms 1100 KB Output is correct
8 Correct 37 ms 7240 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 5052 KB Output is correct
11 Correct 79 ms 7156 KB Output is correct
12 Correct 58 ms 7364 KB Output is correct
13 Correct 54 ms 7404 KB Output is correct
14 Correct 44 ms 7392 KB Output is correct
15 Correct 42 ms 7400 KB Output is correct
16 Correct 43 ms 7372 KB Output is correct
17 Correct 60 ms 7408 KB Output is correct
18 Correct 444 ms 32360 KB Output is correct
19 Correct 13 ms 16588 KB Output is correct
20 Correct 12 ms 940 KB Output is correct
21 Correct 2041 ms 32372 KB Output is correct
22 Correct 683 ms 32368 KB Output is correct
23 Correct 957 ms 32364 KB Output is correct
24 Correct 585 ms 32356 KB Output is correct
25 Correct 517 ms 32452 KB Output is correct
26 Correct 553 ms 32360 KB Output is correct
27 Correct 686 ms 32372 KB Output is correct