Submission #889126

#	Time	Username	Problem	Language	Result	Execution time	Memory
889126		ducngo	Passport (JOI23_passport)	C++17	48 / 100	153 ms	236628 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],xd[2505][2505];
pair<int,int> a[maxn];
int f[2505][2505],l[2505][2505];
queue<pair<int,int>> q[maxn];

int tinh(int u,int v)
{
    if(u==1&&v==n)
    {
        f[u][v]=0;
        return 0;
    }
    if(u>v) return 1e9;
    if(xd[u][v]==1) return f[u][v];
    xd[u][v]=1;
    int val=1e9;
    if(u==v)
    {
        val=min(val,tinh(a[u].first,a[u].second)+1);
    }
    else
    {
        int d=u,c=dpr[u][v];
        val=min(val,tinh(d,c)+1);

        d=dpl[u][v],c=v;
        val=min(val,tinh(d,c)+1);
    }
    f[u][v]=min(f[u][v],val);
    return f[u][v];
}

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;
    }

    for(int i=1;i<=n;i++) tinh(i,i);

    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++) f[i][j]=min(f[i][j-1],f[j][j]);
    }
    memset(xd,0,sizeof(xd));
    for(int i=1;i<=n;i++)
    {
//        xd[i][i]=0;
        tinh(i,i);
    }

    while(q1--)
    {
        int x;
        cin >> x;
        int val=f[x][x];
        if(val>n) cout<<-1<<'\n';
        else cout<<val<<'\n';
    }

//    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)sub3();
}

Compilation message (stderr)

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

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