Submission #1164934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164934		sergiogzz	Sateliti (COCI20_satellti)	C++20	110 / 110	348 ms	68476 KiB

Main

/*
g++ -std=gnu++20 cf2028.cpp -o cf2028 && ./cf2028 < input.txt > output.txt
*/

#include <vector>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <algorithm>
#include <deque>
#include <stack>
#include <set>
#include <math.h>
#include <queue>
#include <cmath>
#include <numeric>
#include <complex>
#include <chrono>
#include <random>
#include <assert.h>
#include <iomanip>
// #include <bits/stdc++.h>


using namespace std;

namespace macros {

    bool printDebug = 0;

    template<typename T>
    void print(T arg) {
        if (!printDebug) return; 
        cout << arg;
    }

    template<typename T, typename... Args>
    void print(T first, Args... args) {
        if (!printDebug) return;
        cout << first << " ";
        print(args...);
    }
    
    // # define M_PI 3.14159265358979323846
    #define optimiza_io \
        cin.tie(0);     \
        ios_base::sync_with_stdio(0);
    #define ll long long
    #define ld double
    #define pb push_back
    #define eb emplace_back
    #define pi pair<ll, ll>
    #define f first
    #define s second
    #define rep(i, a, b) for (ll i = (a); i < (b); i++)
    #define repi(i, a, b) for (ll i = (a); i >= (b); i--)
    #define trav(a, x) for (auto &(a) : (x))
    #define endl "\n"
    #define vi vector<ll>
    #define vvi vector<vi>
    #define vpi vector<pi>
    #define vs vector<string>
    #define sz(a) ((ll)(a).size())
    #define ldd(a) ((ld)(a))
    #define mp(a, b) make_pair((a), (b))
    #define minn(a, b) (a) = min ((a), (b))
    #define maxx(a, b) (a) = max ((a), (b))
    #define all(x) (x).begin(), (x).end()
    #define popcount(x) (ll)__builtin_popcount((x))
    const ld EPS = 1e-7;
    typedef long long C;    
    typedef complex<C> P;
    #define X real()
    #define Y imag()


    template<typename T>
    void printVec(vector<T> arr) {
        trav(u, arr) {
            print(u, " ");
        }
        print(endl);
    }

    // check if 2 ld are equal
    bool equal_ld(ld a, ld b) {
        return abs(a-b) < EPS;
    }
    // for xor hashing
    ll rng(const ll most = INT64_MAX) {
        static mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
        return uniform_int_distribution<ll>(0, most)(gen);
    }

    void modulate(ll &x, const ll &mod) {
        x %= mod;
        x += mod;
        x %= mod;
    }
}
const ll INF = 1e6;
// const ll mod = 1e9+7;
const ll mod = 998244353;
const ll maxn = 3e5+10;

using namespace macros;


// solve
struct HashedString {
    // change M and B if you want
    static const long long M = 1e9 + 9;
    static long long B;

    // pow[i] contains B^i % M
    static vector<long long> pow;

    // p_hash[i] is the hash of the first i characters of the given string
    vector<long long> p_hash;

    // can be vi too
    HashedString(const string &s) : p_hash(s.size() + 1) {
        while (pow.size() <= s.size()) { pow.push_back((pow.back() * B) % M); }

        p_hash[0] = 0;
        for (int i = 0; i < s.size(); i++) {
            p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
        }
    }

    HashedString(const vi &s) : p_hash(s.size() + 1) {
        while (pow.size() <= s.size()) { pow.push_back((pow.back() * B) % M); }

        p_hash[0] = 0;
        for (int i = 0; i < s.size(); i++) {
            p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
        }
    }

    // r inclusive
    long long get_hash(int start, int end) {
        long long raw_val = (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
        return (raw_val % M + M) % M;
    }
};

long long HashedString::B = rng(HashedString::M - 1);
vector<long long> HashedString::pow = {1};


void solve() {
    ll n, m;
    cin >> n >> m;
    vs mat(n);
    trav(u, mat) {
        cin >> u;
        u += u;
    }

    rep(i, 0, n) {
        mat.pb(mat[i]);
    }

    vector<HashedString> ha, haCols;
    vvi cols(m, vi(2*n)); // transposed

    for (auto u : mat) {
        ha.emplace_back(u);
    }

    // start j
    rep(j, 0, m) {
        rep(i, 0, 2*n) {
            cols[j][i] = ha[i].get_hash(j, j+m-1); 
        }
    }

    rep(j, 0, m) {
        haCols.emplace_back(cols[j]);
    }
    pi ans = mp(0,0);

    auto getHashCols = [&] (pi &dir, ll mid) {
        return haCols[dir.s].get_hash(dir.f , dir.f + mid);
    };

    auto getHash = [&] (pi &dir, ll difRow, ll mid) {
        return ha[dir.f + difRow].get_hash(dir.s , dir.s + mid);
    };

    auto check = [&] (pi curr) {
        
        // BS over colums, find first diff
        ll l = 0, r = n-1, mid;
        ll difRow = n;

        while (l <= r) {
            mid = (r-l) / 2 + l;
            print("l = ", l, " ");
            print("r = ", r, " ");
            print("mid = ", mid, " ", endl);
            if (getHashCols(ans, mid) == getHashCols(curr, mid)) {
                l = mid+1;
                print(" - equal", endl);
            } else {
                minn(difRow, mid);
                print(" - dif, interesting", endl);
                r = mid-1;
            }
        }
        print("got", difRow, endl);

        if (difRow == n) return false;

        print(endl, "---", endl);
        l = 0, r = m-1;
        ll difCol = m;
        while (l <= r) {
            mid = (r-l) / 2 + l;
            print("l = ", l, " ");
            print("r = ", r, " ");
            print("mid = ", mid, " ", endl);
            if (getHash(ans, difRow, mid) == getHash(curr, difRow, mid)) {
                l = mid+1;
                print(" - equal", endl);
            } else {
                minn(difCol, mid);
                print(" - dif, interesting", endl);
                r = mid-1;
            }
        }

        if (difCol == m) return false;

        bool result = (
            mat[curr.f + difRow][curr.s + difCol]
            <
            mat[ans.f + difRow][ans.s + difCol]
        );
        print("result = ", result, endl);
        return result;
    };

    rep(i, 0, n) {
        rep(j, 0, m) {
            if (i == j && i == 0) continue; // first assumed to be smaller
            print(i, j, ": ", endl);
            if (check(mp(i, j))) {
                ans = mp(i, j);
            }

            print(endl," ..-.-.-.-   ", endl, endl);
        }
    }

    rep(i, 0, n) {
        rep(j, 0, m) {
            cout << mat[i + ans.f][j + ans.s];
        }
        cout << endl;
    }
}
//

/*
    NEW ME: 
    - Read test cases and experiment with them, use your page 2!!!
    - Ask questions. What to do to achieve this? What's different from usual slower X strat?
    - And ofc, observations
    - Long, Unnecesary coding is not needed!

    ALWAYS REMEMBER:
    - Focus on the target at hand! ---- Making observations? Making formula for X? Write your target down!
    - Simplify before coding
    - Check all test cases!
    - Divide problema dificil en problemas pequeños. POR PARTES!
    - OBSERVATIONS: Recuerda el significado de su nombre
    - EDGE CASES: Yes
    - Calm down

    - Sometimes try formulazo. Intenta representar el valor de manera matemática at some point.
        - Luego intenta derivar formula o simplificarla, ya de ahí tal vez ya queda el problema
        - Formulazo o upper limits!
    - for debugging, read code first before just printing everything haha
    - Even if you find a solution, is the process you made necessary? Is there a way to simplify the process or omit some steps?
    - If greedy, really check if you cannot phantom a possible edge case where it is out of your control
    - Write down the formulas better to facilitate coding
    - primero itera los bits en bitmasking!
    - Si quiero hacer greedy, piensa en "cuando es que me conviene hacer x?"

    OTHER
    - its doable
    - link your ideas, dont forget them
    - remember key aspects, think of even more, optimal

*/


signed main() {
    optimiza_io

    bool file = 0;
    if (file) {
        freopen("lightsout.in", "r", stdin);
        freopen("lightsout.out", "w", stdout);
    }

    bool multipleTestCases = 0;
    printDebug = 0;

    int t = 1;
    if (multipleTestCases) {
        cin >> t;
    }

    rep(i, 0, t) {
        print("\n---------------------\n");
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:305:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  305 |         freopen("lightsout.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:306:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  306 |         freopen("lightsout.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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