Submission #889121

#	Time	Username	Problem	Language	Result	Execution time	Memory
889121		ducngo	Passport (JOI23_passport)	C++17	40 / 100	197 ms	214052 KiB

passport

#include <bits/stdc++.h>
#define getbit(i, j) ((i >> j) & 1)
#define maxn 200005
#define name "Passport"
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long GetRandom(long long l, long long r)
{
    return uniform_int_distribution<long long> (l, r)(rng);
}

int n,q1;
int dpl[2505][2505],dpr[2505][2505];
pair<int,int> a[maxn];
int f[2505][2505];
queue<pair<int,int>> q[maxn];
void sub3()
{
    for(int i=1;i<=n;i++)
    {
        dpl[i][i]=a[i].first;
        dpr[i][i]=a[i].second;
        for(int j=i+1;j<=n;j++)
        {
            dpl[i][j]=dpl[i][j-1];
            if(dpl[i][j]>a[j].first)
            {
                dpl[i][j]=a[j].first;
            }

            dpr[i][j]=dpr[i][j-1];
            if(dpr[i][j]<a[j].second)
            {
                dpr[i][j]=a[j].second;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) f[i][j]=1e9;
    }
    int xp;
    cin >> xp;
    int k=0;
    f[xp][xp]=0;
    q[0].push({xp,xp});
    while(k<n)
    {
        while(q[k].size())
        {
            int u=q[k].front().first,v=q[k].front().second;
//            cout<<u<<' '<<v<<' '<<f[u][v]<<' '<<dpl[u][v]<<' '<<dpr[u][v]<<'\n';
            q[k].pop();
            if(u>v) continue;
            if(f[u][v]!=k) continue;
            if(u==v)
            {
                int d=a[u].first,c=a[u].second;
                if(f[d][c]>k+1)
                {
                    f[d][c]=k+1;
                    q[k+1].push({d,c});
                }
                continue;
            }
            int d=u,c=dpr[u][v];
//            if(u==2&&v==3) cout<<d<<' '<<c<<' '<<f[d][c]<<'\n';
            if(f[d][c]>k+1)
            {
                f[d][c]=k+1;
                q[k+1].push({d,c});
            }
            d=dpl[u][v],c=v;
//            if(u==2&&v==3) cout<<d<<' '<<c<<' '<<f[d][c]<<'\n';
            if(f[d][c]>k+1)
            {
                f[d][c]=k+1;
                q[k+1].push({d,c});
            }
            d=u,c=v;
            if(d<c)
            {

                if(f[d+1][c]>k)
                {
                    f[d+1][c]=k;
                    q[k].push({d+1,c});
                }
//                if(u==2&&v==3) cout<<d<<' '<<c-1<<' '<<f[d][c-1]<<'\n';
                if(f[d][c-1]>k)
                {
                    f[d][c-1]=k;
                    q[k].push({d,c-1});
                }
            }
        }
        k++;
    }
    if(f[1][n]==1e9) cout<<-1;
    else cout<<f[1][n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i].first >> a[i].second;
    }
    cin >> q1;
    if(n<=2500&&q1==1)sub3();
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46