Submission #1096541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096541		dwuy	Matching (CEOI11_mat)	C++14	100 / 100	483 ms	53664 KiB

mat

    #include <bits/stdc++.h>
    #define fi first
    #define se second
    using namespace std;

    struct BIT{
        int n;
        vector<int> tree;
        
        BIT(int n = 0){
            this->n = n;
            this->tree.assign(n + 5, 0);
        }

        void update(int idx, int val){
            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;
        }
    };

    typedef pair<int, int> pii;
    const int MX = 1000005;
    int n, m;
    int l = 1, r = 0, u = 1, v = 0;
    int a[MX], b[MX], p[MX];
    int pa[MX];
    BIT A, B;

    int Ga(int fx, int fy){
        while(r < fy) r++, A.update(a[r], 1);
        while(l < fx) A.update(a[l], -1), l++;
        return A.get(a[fy]);
    }

    int Gb(int fx, int fy){
        while(v < fy) v++, B.update(b[v], 1);
        while(u < fx) B.update(b[u], -1), u++;
        return B.get(b[fy]);
    }

    int32_t main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0); cout.tie(0);

        cin >> n >> m; 
        vector<int> rv(m);
        cin.ignore();
        string s; getline(cin, s); s += ' ';
        for(int i=0, j=1, cur=0; i<(int)s.size(); i++) if(s[i] != ' '){
            cur = cur*10 + s[i] - '0';
            if(s[i + 1] == ' ') a[cur] = j, j++, cur = 0;
        }
        getline(cin, s); s += ' ';
        for(int i=0, j=1; i<(int)s.size(); i++) if(s[i] != ' '){
            b[j] = b[j]*10 + s[i] - '0';
            if(s[i + 1] == ' ') rv[j - 1] = b[j], j++;
        }
        sort(rv.begin(), rv.end());
        for(int i=1; i<=m; i++) b[i] = lower_bound(rv.begin(), rv.end(), b[i]) - rv.begin() + 1;
        A = BIT(n);
        for(int i=1; i<=n; i++) pa[i] = Ga(1, i);
        l = u = 1, r = v = 0;
        A = BIT(n);
        B = BIT(m);
        int l = 1, r = 0, u = 1, v = 0;
        for(int i=2, j=0; i<=n; i++){
            while(j != 0 && pa[j + 1] != Ga(i - j, i)) j = p[j];
            if(pa[j + 1] == Ga(i - j, i)) p[i] = ++j;
        }
        vector<int> ans;
        for(int i=1, j=0; i<=m; i++){
            while(j != 0 && pa[j + 1] != Gb(i - j, i)) j = p[j];
            if(pa[j + 1] == Gb(i - j, i)) j++;
            if(j == n){
                ans.push_back(i - n + 1);
                j = p[j];
            }
        }

        cout << ans.size() << endl;
        for(int x: ans) cout << x << ' ';

        return 0;
    }

Compilation message (stderr)

mat.cpp: In function 'int32_t main()':
mat.cpp:70:13: warning: unused variable 'l' [-Wunused-variable]
   70 |         int l = 1, r = 0, u = 1, v = 0;
      |             ^
mat.cpp:70:20: warning: unused variable 'r' [-Wunused-variable]
   70 |         int l = 1, r = 0, u = 1, v = 0;
      |                    ^
mat.cpp:70:27: warning: unused variable 'u' [-Wunused-variable]
   70 |         int l = 1, r = 0, u = 1, v = 0;
      |                           ^
mat.cpp:70:34: warning: unused variable 'v' [-Wunused-variable]
   70 |         int l = 1, r = 0, u = 1, v = 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