Submission #892170

#	Time	Username	Problem	Language	Result	Execution time	Memory
892170		taichi123	Matching (CEOI11_mat)	C++14	100 / 100	643 ms	43584 KiB

mat

#include <bits/stdc++.h>

using namespace std;

// #define int int64_t
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define sz(a) (int)a.size()
#define mask(i) ((1LL) << (i))
#define bit(x, i) ((x) >> (i) & (1LL))
#define all(x) (x).begin(),(x).end()
#define debug(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T> 
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }
template <class T> 
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }

void file() {
    #define task "aa"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
}

const int INF = 3e18 + 5062007;
const int MOD = 1e9 + 7;
const int MAX = 1e6 + 5;


struct BIT{ 
    int n, l, r;
    vector<int> a;
    vector<int> tree;
 
    BIT(int n, int *a){
        this->n = n;
        this->l = this->r = 0;
        this->a.assign(n+5, 0);
        this->tree.assign(n+5, 0);
        for(int i=1; i<=n; i++) this->a[i] = a[i];
    }
 
    void add(int idx, int val){
        if(idx==0) return;
        for(; idx<=n; idx+=-idx&idx) tree[idx] += val;
    }
 
    int get(int idx){
        int res = 0;
        for(; idx; idx-=-idx&idx) res += tree[idx];
        return res;
    }
 
    int order(int u, int v, int x){
        while(r<v) r++, add(a[r], 1);
        while(l>u) l--, add(a[l], 1);
        while(r>v) add(a[r], -1), r--;
        while(l<u) add(a[l], -1), l++;
        return get(x);
    }
};

int n, m, a[MAX], b[MAX], c[MAX], pi[MAX];
vector<int> v;
void solve(int test_case) {
    cin >> n >> m;
    FOR(i, 1, n) {
        int x; cin >> x;
        a[x] = i;
    }

    FOR(i, 1, m) {
        cin >> b[i];
        v.push_back(b[i]);
    }
    sort(all(v));
    FOR(i, 1, m) b[i] = lower_bound(all(v), b[i]) - v.begin() + 1;

    BIT A = BIT(n, a);
    BIT B = BIT(n, a);
    for(int i=1; i<=n; i++) pi[i] = 1;
    for(int i=1, j=2; j<=n; ){
        if(A.order(j-i+1, j, a[j]) == B.order(1, i, a[i])) pi[j] = i, i++, j++;
        else if(i!=pi[i-1]+1) i = pi[i-1] + 1;
        else j++;
    }
    for(int i=1; i<=n; i++) c[i] = A.order(1, i, a[i]);
    B = BIT(m, b);
    vector<int> ans;
    for(int i=1, j=1; i<=m;){
        if(B.order(i-j+1, i, b[i]) == c[j]){
            if(j==n) j = pi[j], ans.push_back(i-n+1);
            else i++, j++;
        }
        else if(j!=pi[j-1]+1) j = pi[j-1] + 1;
        else if(j==2) j = 1;
        else i++;
    }
    cout << ans.size() << endl;
    for(int &x: ans) cout << x << ' ';
}

auto main() -> signed {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    file();

    int test = 1; 
    // cin >> test; 
    for (int _ = 1; _ <= test; ++_) solve(_);
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}
//567
/*
6 12
2 5 3 4 1 6
10 45 25 30 5 47 31 35 4 50 33 20
*/

Compilation message (stderr)

mat.cpp:36:22: warning: overflow in conversion from 'double' to 'int' changes value from '3.0000000000050621e+18' to '2147483647' [-Woverflow]
   36 | const int INF = 3e18 + 5062007;
      |                 ~~~~~^~~~~~~~~
mat.cpp: In function 'void file()':
mat.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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