oj.uz

Submission #377435

# Submission time Handle Problem Language Result Execution time Memory
377435 2021-03-14T08:11:26 Z ne4eHbKa Sateliti (COCI20_satellti) C++17
50 / 110
 3000 ms 128132 KB 
#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

const int N = 1e3 + 5;
const int NN = 2e3 + 5;

int n, m, nn, mm;
typedef array<array<int, NN>, NN> mt;
mt a[11], A, z;

void combine(mt &a, mt &b, mt &c, int dx, int dy) {
    vector<pii> f;
    for(int i = 0; i + dx < nn; ++i)
        for(int j = 0; j + dy < mm; ++j)
            f.push_back({i, j});
    sort(bnd(f), [&] (const pii &l, const pii &r) {
        int &lfi = a[l.ft][l.sd], &lse = b[l.ft + dx][l.sd + dy];
        int &rfi = a[r.ft][r.sd], &rse = b[r.ft + dx][r.sd + dy];
        return lfi == rfi ? lse < rse : lfi < rfi;
    });
    vector<int> e(len(f));
    for(int i = 0, j = 0; i < len(f); ++i) {
        j += i && (a[f[i - 1].ft]     [f[i - 1].sd]      != a[f[i].ft]     [f[i].sd] ||
                   b[f[i - 1].ft + dx][f[i - 1].sd + dy] != b[f[i].ft + dx][f[i].sd + dy]);
        e[i] = j;
    }
    for(int i = 0; i < len(f); ++i)
        c[f[i].ft][f[i].sd] = e[i];
}

void solve() {
    cin >> n >> m;
    for(int i = 0; i < n + n; ++i) {
        for(int j = 0; j < m + m; ++j) {
            if(i < n && j < m) {
                char c; cin >> c;
                a[0][i][j] = c == '.';
            } else
                a[0][i][j] = a[0][i % n][j % m];
            A[i][j] = 0;
        }
    }
    z = a[0];
    nn = n << 1;
    mm = m << 1;
    for(int i = 0, u = m; ; ++i) {
        if(i) combine(a[i - 1], a[i - 1], a[i], 0, 1 << i - 1);
        if(u & 1 << i) {
            combine(a[i], A, A, 0, 1 << i);
            u ^= 1 << i;
            if(!u) break;
        }
    }
    a[0] = A;
    for(int i = 0; i < nn; ++i)
        for(int j = 0; j < mm; ++j)
            A[i][j] = 0;
    for(int i = 0, u = n; ; ++i) {
        if(i) combine(a[i - 1], a[i - 1], a[i], 1 << i - 1, 0);
        if(u & 1 << i) {
            combine(a[i], A, A, 1 << i, 0);
            u ^= 1 << i;
            if(!u) break;
        }
    }
    int x = 0, y = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(A[i][j] < A[x][y])
                x = i, y = j;
    for(int i = 0; i < n; ++i, cout << '\n')
        for(int j = 0; j < m; ++j) cout << (z[x + i][y + j] ? '.' : '*');
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:73:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   73 |         if(i) combine(a[i - 1], a[i - 1], a[i], 0, 1 << i - 1);
      |                                                         ~~^~~
Main.cpp:85:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   85 |         if(i) combine(a[i - 1], a[i - 1], a[i], 1 << i - 1, 0);
      |                                                      ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 34776 KB Output is correct
2 Correct 44 ms 34456 KB Output is correct
3 Correct 42 ms 34456 KB Output is correct
4 Correct 40 ms 34456 KB Output is correct
5 Correct 44 ms 34708 KB Output is correct
6 Correct 50 ms 34708 KB Output is correct
7 Correct 40 ms 34708 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 34776 KB Output is correct
2 Correct 44 ms 34456 KB Output is correct
3 Correct 42 ms 34456 KB Output is correct
4 Correct 40 ms 34456 KB Output is correct
5 Correct 44 ms 34708 KB Output is correct
6 Correct 50 ms 34708 KB Output is correct
7 Correct 40 ms 34708 KB Output is correct
8 Correct 1627 ms 71512 KB Output is correct
9 Correct 51 ms 33240 KB Output is correct
10 Correct 37 ms 52460 KB Output is correct
11 Correct 954 ms 71412 KB Output is correct
12 Correct 891 ms 72224 KB Output is correct
13 Correct 1008 ms 72556 KB Output is correct
14 Correct 1032 ms 72692 KB Output is correct
15 Correct 1237 ms 72760 KB Output is correct
16 Correct 1156 ms 72692 KB Output is correct
17 Correct 951 ms 72672 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 34776 KB Output is correct
2 Correct 44 ms 34456 KB Output is correct
3 Correct 42 ms 34456 KB Output is correct
4 Correct 40 ms 34456 KB Output is correct
5 Correct 44 ms 34708 KB Output is correct
6 Correct 50 ms 34708 KB Output is correct
7 Correct 40 ms 34708 KB Output is correct
8 Correct 1627 ms 71512 KB Output is correct
9 Correct 51 ms 33240 KB Output is correct
10 Correct 37 ms 52460 KB Output is correct
11 Correct 954 ms 71412 KB Output is correct
12 Correct 891 ms 72224 KB Output is correct
13 Correct 1008 ms 72556 KB Output is correct
14 Correct 1032 ms 72692 KB Output is correct
15 Correct 1237 ms 72760 KB Output is correct
16 Correct 1156 ms 72692 KB Output is correct
17 Correct 951 ms 72672 KB Output is correct
18 Execution timed out 3031 ms 128132 KB Time limit exceeded
19 Halted 0 ms 0 KB -