# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
830853 |
2023-08-19T11:46:13 Z |
dwuy |
Matching (CEOI11_mat) |
C++14 |
|
603 ms |
41120 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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
812 KB |
Output is correct |
2 |
Correct |
4 ms |
788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
788 KB |
Output is correct |
2 |
Correct |
4 ms |
816 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
5080 KB |
Output is correct |
2 |
Correct |
30 ms |
5032 KB |
Output is correct |
3 |
Correct |
68 ms |
7320 KB |
Output is correct |
4 |
Correct |
69 ms |
7320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
5748 KB |
Output is correct |
2 |
Correct |
57 ms |
7072 KB |
Output is correct |
3 |
Correct |
42 ms |
7016 KB |
Output is correct |
4 |
Correct |
41 ms |
5756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
5600 KB |
Output is correct |
2 |
Correct |
38 ms |
5472 KB |
Output is correct |
3 |
Correct |
50 ms |
6312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
32104 KB |
Output is correct |
2 |
Correct |
601 ms |
41120 KB |
Output is correct |
3 |
Correct |
202 ms |
26000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
279 ms |
31000 KB |
Output is correct |
2 |
Correct |
339 ms |
24528 KB |
Output is correct |
3 |
Correct |
603 ms |
38044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
239 ms |
27944 KB |
Output is correct |
2 |
Correct |
205 ms |
27020 KB |
Output is correct |
3 |
Correct |
278 ms |
32992 KB |
Output is correct |
4 |
Correct |
372 ms |
39524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
27900 KB |
Output is correct |
2 |
Correct |
302 ms |
33740 KB |
Output is correct |
3 |
Correct |
98 ms |
13944 KB |
Output is correct |
4 |
Correct |
402 ms |
38036 KB |
Output is correct |