Submission #892166

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
892166	2023-12-25T02:52:11 Z	taichi123	Matching (CEOI11_mat)	C++14	100 / 100	565 ms	61280 KB

/// 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.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2528 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2524 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3124 KB	Output is correct
2	Correct	4 ms	3100 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3100 KB	Output is correct
2	Correct	4 ms	3128 KB	Output is correct
3	Correct	1 ms	2520 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	9056 KB	Output is correct
2	Correct	32 ms	8368 KB	Output is correct
3	Correct	69 ms	12456 KB	Output is correct
4	Correct	69 ms	12576 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	9016 KB	Output is correct
2	Correct	60 ms	12328 KB	Output is correct
3	Correct	42 ms	12308 KB	Output is correct
4	Correct	36 ms	9008 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	9164 KB	Output is correct
2	Correct	39 ms	9488 KB	Output is correct
3	Correct	52 ms	10544 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	269 ms	42656 KB	Output is correct
2	Correct	565 ms	61280 KB	Output is correct
3	Correct	213 ms	37520 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	269 ms	39356 KB	Output is correct
2	Correct	331 ms	35076 KB	Output is correct
3	Correct	547 ms	51316 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	238 ms	35748 KB	Output is correct
2	Correct	185 ms	35308 KB	Output is correct
3	Correct	267 ms	46804 KB	Output is correct
4	Correct	360 ms	53724 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	219 ms	35980 KB	Output is correct
2	Correct	274 ms	48124 KB	Output is correct
3	Correct	101 ms	20024 KB	Output is correct
4	Correct	423 ms	56128 KB	Output is correct

Submission #892166

Compilation message