Submission #1178198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178198		khongphaifu	Matching (CEOI11_mat)	C++20	0 / 100	586 ms	30396 KiB

mat

#include "bits/stdc++.h"
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define OFF(x, i) ((x) & ~(1LL << (i)))
#define ON(x, i) ((1LL << (i)) | (x))
#define CNT(x) __builtin_popcountll(x)
#define task ""
#define endl '\n'
#define F first
#define S second
#define all(v) (v).begin(), (v).end()
#define pb emplace_back
#define log2(x) 63 - __builtin_clzll(x)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define FORD(i, l, r) for(int i = (l), _r = (r); i >= _r; --i)

using namespace std;
using ll = long long;
using pii = pair <int, int>;
using vi = vector <int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r)
{
    return l + rng() % (r - l + 1);
}

template<class T> bool maxi(T& u, T v)
{
    if(u >= v) return false;
    return u = v, true;
}

template<class T> bool mini(T& u, T v)
{
    if(u <= v) return false;
    return u = v, true;
}

const int N = 1e6 + 6;
int n, m, H[N], G[N];

void Sub1()
{
    vector <int> L;
    for (int s = 1; s <= m - n + 1; ++s)
    {
        bool ok = true;
        for (int i = 1; i <= n and ok; ++i)
            for (int j = i + 1; j <= n and ok; ++j)
            {
                if (bool(G[i + s - 1] < G[j + s - 1]) != bool(H[i] < H[j]))
                    ok = false;
            }
        if (ok) L.pb(s);
    }
    cout << L.size() << '\n';
    if (L.empty()) return;
    for (int x : L) cout << x << ' ';
}

int Pos[N];

void Sub2()
{
    vector <int> L;
    for (int i = 1; i <= n; ++i) Pos[H[i]] = i;
    for (int s = 1; s <= m - n + 1; ++s)
    {
        vector <pii> L2;
        bool ok = true;
        for (int i = 1; i <= n; ++i) L2.pb(G[i + s - 1], i);
        sort(all(L2));
        for (int i = 1; i <= n; ++i)
            if (L2[i - 1].S != Pos[i])
            {
                ok = false;
                break;
            }
        if (ok) L.pb(s);
    }
    cout << L.size() << '\n';
    if (L.empty()) return;
    for (int x : L) cout << x << ' ';
}

int Base;
const int MOD = 1e9 + 7;
void Add(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}
int Pow[N];
struct Node
{
    int Hash, Len;
}IT[N << 2];
Node operator + (const Node &L, const Node &R)
{
    Node ans;
    //ans.Hash = ((ll) L.Hash * Pow[R.Len] % MOD + R.Hash) % MOD;
    ans.Hash = (ll) L.Hash * Pow[R.Len] % MOD;
    Add(ans.Hash, R.Hash);
    ans.Len = L.Len + R.Len;
    return ans;
}
void Upd(int k, int l, int r, int u, int v)
{
    if (u < l || u > r) return;
    if (l == r)
    {
        if (v == 0) IT[k] = {0, 0};
        else IT[k] = {v, 1};
        return;
    }
    int mid = l + r >> 1;
    Upd(k << 1, l, mid, u, v);
    Upd(k << 1 | 1, mid + 1, r, u, v);
    IT[k] = IT[k << 1] + IT[k << 1 | 1];
}

void SubFull()
{
    vector <int> C(G + 1, G + 1 + m);
    sort(all(C));
    C.erase(unique(all(C)), C.end());
    for (int i = 1; i <= m; ++i)
        G[i] = lower_bound(all(C), G[i]) - C.begin() + 1;

    vector <int> L;

    for (int i = 1; i <= n; ++i) Pos[H[i]] = i;
    Pow[0] = 1;
    for (int i = 1; i <= m; ++i) Pow[i] = (ll) Pow[i - 1] * Base % MOD;
    int Pattern = 0;
    int Shift = 0;
    for (int i = 1; i <= n; ++i)
    {
        Add(Pattern, (ll) Pos[i] * Pow[n - i] % MOD);
        Add(Shift, Pow[n - i]);
    }

    for (int i = 1; i <= n; ++i)
        Upd(1, 1, m, G[i], i);

    if (IT[1].Hash == Pattern) L.pb(1);
    for (int i = 2; i <= m - n + 1; ++i)
    {
        Add(Pattern, Shift);
        Upd(1, 1, m, G[i - 1], 0);
        Upd(1, 1, m, G[i + n - 1], i + n - 1);
        if (IT[1].Hash == Pattern) L.pb(i);
    }

    printf("%d\n", L.size());
    if (L.empty()) return;
    for (int x : L) printf("%d ", x);
}

signed main()
{
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &H[i]);
    for (int i = 1; i <= m; ++i) scanf("%d", &G[i]);

    Base = m + 1;

    //Sub3(); /// O(m * n log m)
    SubFull(); /// O(m log m)

    return 0;
}

Compilation message (stderr)

mat.cpp: In function 'void SubFull()':
mat.cpp:156:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  156 |     printf("%d\n", L.size());
      |             ~^     ~~~~~~~~
      |              |           |
      |              int         std::vector<int>::size_type {aka long unsigned int}
      |             %ld
mat.cpp: In function 'int main()':
mat.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
mat.cpp:169:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |     for (int i = 1; i <= n; ++i) scanf("%d", &H[i]);
      |                                  ~~~~~^~~~~~~~~~~~~
mat.cpp:170:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     for (int i = 1; i <= m; ++i) scanf("%d", &G[i]);
      |                                  ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10