QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#65992#1964. Stock Price Predictiondlg#TL 0ms0kbC++173.1kb2022-12-05 14:07:022022-12-05 14:07:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-05 14:07:03]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-12-05 14:07:02]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define fi first
#define se second
#define sp ' '
#define endl '\n'
#define loop(i, l, r) for(int i=(int)(l); i<=(int)(r); i++)
#define rloop(i, l, r) for(int i=(int)(l); i>=(int)r; i--)
#define all(x) (x).begin(), (x).end()

ostream &operator<<(ostream &os, vector<int> a) {
    os << "[";
    for (auto it: a) os << it << sp;
    os << "]";
    return os;
}

const int INF = numeric_limits<int>::max() / 2;


const int N = 1e6 + 5;

struct Fenwick {
    int f[N];

    void update(int i, int val) {
        for (; i < N; i += i & (-i)) f[i] += val;
    }

    int getR(int i) {
        auto rec = get(i);
        auto rec2 = get(i-1);
        return rec+rec2;
    }

private:
    int get(int i) {
        int ret = 0;
        for (; i; i -= i & -i) ret += f[i];
        return ret;
    }
};

vector<int> dual(vector<int> &a, vector<int> &b, int w[], int sta, bool spec){

    Fenwick fa,fb;
    int lenPref = 0;

    // posB must be posB - 1
    auto del = [&](int posB, int lenDel) {
        loop(i, 1, lenDel) fa.update(a[lenPref - i + 1], -1);

        int staB = posB - lenPref + 1;
        loop(i, 1, lenDel) fb.update(b[staB + i - 1], -1);

        lenPref -= lenDel;
    };

    auto getLenJump = [&](int x){
        return x-w[x];
    };

    vector<int> ret;
    loop(i,sta,b.size()-1){
        if (lenPref==a.size()-1){
            del(i-1,getLenJump(lenPref));
        }
        while(true){
            int rankA = fa.getR(a[lenPref+1]);
            int rankB = fb.getR(b[i]);
            if (rankA==rankB) break;
            auto len = getLenJump(lenPref);
            del(i-1,len);
        }
        fa.update(a[lenPref+1],1);
        fb.update(b[i],1);
        lenPref++;
        if (spec) w[i] = lenPref;
        if (lenPref==a.size()-1){
            ret.push_back(i);
        }
    }

    return ret;
}

struct KMPx {
    int w[10005];

    void init(vector<int> &s) {
        w[0] = -1;
        w[1] = 0;
        dual(s,s,w,2,true);
    }
} kmp;

//3 1 0 1
//5 2 1 1
//5 1 0 1
//5 0 -1 1
//0 1 1 2 0

void enc(vector<int> &ori) {
    auto inp = ori;
    sort(all(inp));
    inp.erase(unique(all(inp)), inp.end());

    for (auto &it: ori) it = lower_bound(all(inp), it) - inp.begin();
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef LOCAL
    freopen("1test.inp", "r", stdin);
#endif
    Fenwick fa, fb;
    int n, m;
    cin >> n >> m;


    vector<int> a = {-INF}, b = {-INF};
    loop(i, 1, n) {
        int t;
        cin >> t;
        a.push_back(t);
    }

    loop(i, 1, m) {
        int t;
        cin >> t;
        b.push_back(t);
    }

    if (n > m) { // clearly true
        cout << 0 << endl;
        return 0;
    }

    enc(a);
    enc(b);

    kmp.init(a);

//    loop(i,1,n) cout << kmp.w[i] << sp;
//    cout << endl;
//    exit(0);
    // 0 1 2 3 1
    vector<int> ans = dual(a,b,kmp.w,1,0);

    if (ans.empty()){
        cout << 0 << endl;
        exit(0);
    }

    for(auto it:ans) cout << it-n+1 << sp;
    cout << endl;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:


result: