Submission #1183267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183267		aminjon__	Matching (CEOI11_mat)	C++17	45 / 100	2094 ms	67412 KiB

mat

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define endl '\n'

#pragma GCC optimize("O3")

typedef unsigned int uint;
typedef int ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define oset tree<pair<int,int>, null_type,less< pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> 
using namespace __gnu_pbds;

void solve()
{
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    oset s;

    vector<ll> ans;
    
    
    
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
        if (i < n)
        {
            s.insert({b[i], i});
            continue;
        }
         s.insert({b[i], i});
        if (i > n)
        {
            s.erase({b[i - n], i - n});
        }
        
        bool ok2 = 1;
        for(int j = 1;j <= min(n,400);j++){
            
            rng();
            ll el = (rng()%n);
            ll ind = s.find_by_order(el)->second; 
            if( a[el+1] != ind-(i-n)  ){
                ok2=0;
                break;
            }
        }
        
        
        
        if(!ok2)continue;
        
        bool ok = 1;
        ll cur = 0;
        for (auto g : s)
        {
            cur++;
            if (g.second != a[cur] + (i - n))
            {
                ok = 0;
                break;
            }
        }
        if (ok)
        {
            ans.push_back(i - n + 1);
        }
    }

    cout << ans.size() << endl;
    for (auto g : ans)
    {
        cout << g << ' ';
    }
}
signed main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10