oj.uz

Submission #892170

# Submission time Handle Problem Language Result Execution time Memory
892170 2023-12-25T03:09:22 Z taichi123 Matching (CEOI11_mat) C++14
100 / 100
 643 ms 43584 KB 
#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

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

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7004 KB Output is correct
2 Correct 9 ms 6744 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7004 KB Output is correct
2 Correct 6 ms 7004 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 11464 KB Output is correct
2 Correct 43 ms 10960 KB Output is correct
3 Correct 80 ms 13988 KB Output is correct
4 Correct 86 ms 13920 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13932 KB Output is correct
2 Correct 70 ms 11168 KB Output is correct
3 Correct 62 ms 11472 KB Output is correct
4 Correct 45 ms 13140 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 14032 KB Output is correct
2 Correct 50 ms 13908 KB Output is correct
3 Correct 62 ms 11360 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 30592 KB Output is correct
2 Correct 643 ms 43520 KB Output is correct
3 Correct 238 ms 18224 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 31056 KB Output is correct
2 Correct 400 ms 20420 KB Output is correct
3 Correct 635 ms 42536 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 24228 KB Output is correct
2 Correct 237 ms 31308 KB Output is correct
3 Correct 324 ms 23644 KB Output is correct
4 Correct 475 ms 43584 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 26804 KB Output is correct
2 Correct 321 ms 23712 KB Output is correct
3 Correct 125 ms 20164 KB Output is correct
4 Correct 490 ms 41532 KB Output is correct