oj.uz

답안 #377457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
377457 2021-03-14T08:41:20 Z ne4eHbKa Sateliti (COCI20_satellti) C++17
50 / 110
 3000 ms 235932 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;
const int K = 4e6 + 5;

int n, m, nn, mm;
typedef array<array<int, NN>, NN> mt;
mt a[11], A, z;
int fst[K], lst[K], nxt[K], vl[K], t;

void add(int i, int j) {
    if(fst[i] < 0) {
        fst[i] = lst[i] = t;
    } else {
        nxt[lst[i]] = t;
        lst[i] = t;
    }
    vl[t++] = j;
}

vector<int> e;

void iterate(int i) {
    if(fst[i] < 0) return;
    for(int j = fst[i]; ; j = nxt[j]) {
        e.push_back(vl[j]);
        if(j == lst[i]) return;
    }
}

typedef pair<pii, pii> ppp;
vector<ppp> f;

void combine(mt &a, mt &b, mt &c, int dx, int dy) {
    f.clear();
    for(int i = 0; i + dx < nn; ++i)
        for(int j = 0; j + dy < mm; ++j)
            f.push_back({{a[i][j], b[i + dx][j + dy]}, {i, j}});
    int k = len(f);
    memset(fst, -1, sizeof fst); t = 0;
    for(int i = 0; i < k; ++i)
        add(f[i].ft.sd, i);
    e.clear();
    for(int i = 0; i < K; ++i)
        iterate(i);
    memset(fst, -1, sizeof fst); t = 0;
    for(int i : e)
        add(f[i].ft.ft, i);
    e.clear();
    for(int i = 0; i < K; ++i)
        iterate(i);
    for(int i = 0, j = 0; i < k; ++i) {
        auto &g = f[e[i]];
        if(i && g.ft != f[e[i - 1]].ft)
            ++j;
        c[g.sd.ft][g.sd.sd] = j;
    }
}

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:104:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  104 |         if(i) combine(a[i - 1], a[i - 1], a[i], 0, 1 << i - 1);
      |                                                         ~~^~~
Main.cpp:116:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  116 |         if(i) combine(a[i - 1], a[i - 1], a[i], 1 << i - 1, 0);
      |                                                      ~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 625 ms 50544 KB Output is correct
2 Correct 682 ms 50288 KB Output is correct
3 Correct 691 ms 50416 KB Output is correct
4 Correct 680 ms 50308 KB Output is correct
5 Correct 673 ms 50660 KB Output is correct
6 Correct 666 ms 50612 KB Output is correct
7 Correct 672 ms 50592 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 625 ms 50544 KB Output is correct
2 Correct 682 ms 50288 KB Output is correct
3 Correct 691 ms 50416 KB Output is correct
4 Correct 680 ms 50308 KB Output is correct
5 Correct 673 ms 50660 KB Output is correct
6 Correct 666 ms 50612 KB Output is correct
7 Correct 672 ms 50592 KB Output is correct
8 Correct 2031 ms 93376 KB Output is correct
9 Correct 699 ms 49104 KB Output is correct
10 Correct 537 ms 68204 KB Output is correct
11 Correct 1209 ms 93340 KB Output is correct
12 Correct 1180 ms 93648 KB Output is correct
13 Correct 1317 ms 94884 KB Output is correct
14 Correct 1305 ms 94800 KB Output is correct
15 Correct 1479 ms 94804 KB Output is correct
16 Correct 1410 ms 95048 KB Output is correct
17 Correct 1239 ms 94412 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 625 ms 50544 KB Output is correct
2 Correct 682 ms 50288 KB Output is correct
3 Correct 691 ms 50416 KB Output is correct
4 Correct 680 ms 50308 KB Output is correct
5 Correct 673 ms 50660 KB Output is correct
6 Correct 666 ms 50612 KB Output is correct
7 Correct 672 ms 50592 KB Output is correct
8 Correct 2031 ms 93376 KB Output is correct
9 Correct 699 ms 49104 KB Output is correct
10 Correct 537 ms 68204 KB Output is correct
11 Correct 1209 ms 93340 KB Output is correct
12 Correct 1180 ms 93648 KB Output is correct
13 Correct 1317 ms 94884 KB Output is correct
14 Correct 1305 ms 94800 KB Output is correct
15 Correct 1479 ms 94804 KB Output is correct
16 Correct 1410 ms 95048 KB Output is correct
17 Correct 1239 ms 94412 KB Output is correct
18 Execution timed out 3076 ms 235932 KB Time limit exceeded
19 Halted 0 ms 0 KB -