제출 #1078646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1078646		Neco_arc	Sateliti (COCI20_satellti)	C++17	110 / 110	329 ms	61524 KiB

Main

#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Sateliti"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e3 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n, m, N, M;
char a[maxn][maxn];
ll H[maxn][maxn], po[maxn * maxn];
ll Hash[maxn][maxn];

pair<int, int> nex(int x, int y, int len) {
    int k = len / M;
    if(len % M == 0) return {x + k - 1, y + M - 1};
    return {x + k, y + (len % M) - 1};
}

ll getR(int x, int l, int r) {
    if(l > r) return 0;
    return Hash[x][r] - Hash[x][l - 1] * po[r - l + 1];
}

pair<ll, ll> get(int u, int v, int len) {
    ll ans1 = 0, ans2;
    int k = len / M;
    if(k) ans1 = H[u + k - 1][v] - H[u - 1][v] * po[k];
    ans2 = getR(u + k, v, v + (len % M) - 1);

    return {ans1, ans2};
}

int check(int x, int y, int u, int v) {
    int l = 1, r = N * M - 1;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(get(x, y, mid) == get(u, v, mid)) l = mid + 1;
        else r = mid - 1;
    }

    tie(x, y) = nex(x, y, r + 1), tie(u, v) = nex(u, v, r + 1);
    return a[u][v] < a[x][y];
}

ll HASH(string s) {
    ll ans = 0;
    for(char c : s) ans = ans * base + c;
    return ans;
}

void solve()
{

    cin >> n >> m;
    N = n, M = m;

    fi(i, 1, n) fi(j, 1, m) {
        cin >> a[i][j];
        a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];
    }

    n *= 2, m *= 2;

    fi(i, 1, n) {
        fi(j, 1, m) Hash[i][j] = Hash[i][j - 1] * base + a[i][j];
        fi(j, 1, m - M + 1) H[i][j] = H[i - 1][j] * base + getR(i, j, j + M - 1);
    }

    pair<int, int> ans = {1, 1};
    fi(i, 1, N) fi(j, 1, M) {
        if(check(ans.first, ans.second, i, j)) ans = {i, j};
    }

    int u, v; tie(u, v) = ans;
    fi(i, 1, N) fi(j, 1, M) {
        cout << a[u + i - 1][v + j - 1];
        if(j == M) cout << '\n';
    }


}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }

    po[0] = 1;
    fi(i, 1, maxn * maxn) po[i] = po[i - 1] * base;

    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:112:33: warning: iteration 16006 invokes undefined behavior [-Waggressive-loop-optimizations]
  112 |     fi(i, 1, maxn * maxn) po[i] = po[i - 1] * base;
      |                           ~~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:14:38: note: within this loop
   14 | #define fi(i, a, b) for(int i = a; i <= b; i++)
      |                                      ^
Main.cpp:112:5: note: in expansion of macro 'fi'
  112 |     fi(i, 1, maxn * maxn) po[i] = po[i - 1] * base;
      |     ^~

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