oj.uz

답안 #117642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
117642 2019-06-17T03:41:00 Z JohnTitor Matching (CEOI11_mat) C++11
100 / 100
 801 ms 40472 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
using ll=long long;
using ld=long double;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "Matching"
int n, m;
int a[1000002];
int b[1000002];
namespace KMP_log{
    int f[1000002];
    int ft[1000002];
    int pos[1000002];
    void update(int u, int x){
        for(; u<=1000000; u+=u&-u) ft[u]+=x;
    }
    int get(int u){
        int res=0;
        for(; u>0; u-=u&-u) res+=ft[u];
        return res;
    }
    void solve(){
        FOR(i, 1, n){
            pos[i]=get(a[i]);
            update(a[i], 1);
        }
        pos[n+1]=-1;
        FOR(i, 0, 1000000) ft[i]=0;
        int p=0;
        FOR(i, 2, n){
            while(p&&(get(a[i])!=pos[p+1])){
                int nx=f[p];
                while(p>nx){
                    update(a[i-p], -1);
                    p--;
                }
            }
            p++;
            f[i]=p;
            update(a[i], 1);
        }
        FOR(i, 0, 1000000) ft[i]=0;
        p=0;
        vector <int> ans;
        FOR(i, 1, m){
            while(p&&get(b[i])!=pos[p+1]){
                int nx=f[p];
                while(p>nx){
                    update(b[i-p], -1);
                    p--;
                }
            }
            p++;
            if(p==n) ans.pb(i-n+1);
            update(b[i], 1);
        }
        writeln(ans.size());
        for(int x: ans){
            write(x);
            putchar(' ');
        }
    }
};
ll f;
map <int, int> M;
int main(){
    #ifdef Uiharu
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Uiharu
    read(n);
    read(m);
    FOR(i, 1, n){
        int temp;
        read(temp);
        a[temp]=i;
    }
    vector <int> cont;
    FOR(i, 1, m){
        read(b[i]);
        cont.push_back(b[i]);
    }
    sort(cont.begin(), cont.end());
    FOR(i, 1, m) b[i]=lower_bound(cont.begin(), cont.end(), b[i])-cont.begin()+1;
//    FOR(i, 1, m) cerr<<b[i]<<" \n"[i==m];
    KMP_log::solve();
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4224 KB Output is correct
2 Correct 6 ms 4224 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 5 ms 4224 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4352 KB Output is correct
2 Correct 6 ms 4352 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 4736 KB Output is correct
2 Correct 11 ms 4736 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4736 KB Output is correct
2 Correct 11 ms 4736 KB Output is correct
3 Correct 6 ms 4352 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 7788 KB Output is correct
2 Correct 49 ms 7212 KB Output is correct
3 Correct 94 ms 8684 KB Output is correct
4 Correct 94 ms 8752 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 8428 KB Output is correct
2 Correct 85 ms 7916 KB Output is correct
3 Correct 64 ms 8428 KB Output is correct
4 Correct 62 ms 9324 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 8588 KB Output is correct
2 Correct 57 ms 8092 KB Output is correct
3 Correct 77 ms 8044 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 25696 KB Output is correct
2 Correct 735 ms 40472 KB Output is correct
3 Correct 288 ms 18396 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 25760 KB Output is correct
2 Correct 483 ms 19096 KB Output is correct
3 Correct 801 ms 36604 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 353 ms 22176 KB Output is correct
2 Correct 287 ms 29652 KB Output is correct
3 Correct 439 ms 22908 KB Output is correct
4 Correct 412 ms 38500 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 23004 KB Output is correct
2 Correct 401 ms 23260 KB Output is correct
3 Correct 137 ms 13668 KB Output is correct
4 Correct 500 ms 37724 KB Output is correct