Submission #892166

#	Time	Username	Problem	Language	Result	Execution time	Memory
892166		taichi123	Matching (CEOI11_mat)	C++14	100 / 100	565 ms	61280 KiB

mat

/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>
 
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK "test"
 
using namespace std;
 
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
 
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
 
struct BIT{ /// order_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);
    }
};
 
const int MX = 1000005;
int n, m;
int a[MX], b[MX], c[MX];
int pf[MX];
 
void nhap(){
    cin >> n >> m; cin.ignore();
    vector<int> tmp(m);
    string s;
 
    getline(cin, s); s = s + " 0";
    for(int i=1, j=0; j+1<=len(s); j++){
        if(s[j]==' '&&s[j+1]!=' ') a[c[i]] = i, i++;
        else c[i] = c[i]*10 + s[j] - '0';
    }
    getline(cin, s); s = s + " 0";
    for(int i=1, j=0; j+1<len(s); j++){
        if(s[j]==' ' && s[j+1]!=' ') tmp[i-1] = b[i], i++;
        else b[i] = b[i]*10 + s[j] - '0';
    }
 
    sort(tmp.begin(), tmp.end());
    for(int i=1; i<=m; i++){
        b[i] = lower_bound(tmp.begin(), tmp.end(), b[i]) - tmp.begin() + 1;
    }
}
 
void solve(){
    BIT A = BIT(n, a);
    BIT B = BIT(n, a);
    for(int i=1; i<=n; i++) pf[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])) pf[j] = i, i++, j++;
        else if(i!=pf[i-1]+1) i = pf[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 = pf[j], ans.push_back(i-n+1);
            else i++, j++;
        }
        else if(j!=pf[j-1]+1) j = pf[j-1] + 1;
        else if(j==2) j = 1;
        else i++;
    }
    cout << ans.size() << endl;
    for(int &x: ans) cout << x << ' ';
}
 
int32_t main(){
    fastIO;
//    file(TASK);
 
    nhap();
    solve();
 
    return 0;
}

• 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