139882025-01-09 14:18:15BencuA lehető legkevesebb átszállás (50 pont)cpp17Wrong answer 23/50300ms724 KiB
#include <bits/stdc++.h>

using namespace std;
int n,m,s,M[10001],h;
struct vonatok {
    int x;
    int y;
    int szam;
}a[10001];
int helyre(int elso, int utolso) {
    int i=elso,j=utolso,p=elso;
    while (i<j) {
        if(a[i].y>a[j].y) {
            swap(a[i],a[j]);
            if(i==p) {
                p=j;
                i++;
            }
            else {
                p=i;
                j--;
            }
        }
        else if(p==i) j--;
            else i++;
    }
    return p;
}
void QuickSort(int elso,int utolso) {
    if (elso<utolso) {
        int k=helyre(elso,utolso);
        QuickSort(elso,k-1);
        QuickSort(k+1,utolso);
    }
}
void torol(int i) {
    for (int j=i; j<n; j++) {
        a[j].x=a[j+1].x;
        a[j].y=a[j+1].y;
        a[j].szam=a[j+1].szam;
    }
    n--;
}
void be() {
    ifstream f("be.in");
    cin>>n>>m;
    for (int i=1; i<=n; i++) {
        a[i].szam=i;
        cin>>a[i].x>>a[i].y;
    }
    QuickSort(1,n);
    /*for (int i=1; i<n; i++) {
        if (a[i].x==a[i+1].x && a[i].y<a[i+1].y) {
            torol(i);
            i--;
        }
        if (a[i].x==a[i+1].x && a[i].y>a[i+1].y) {
            torol(i+1);
            i--;
        }
    }*/
}

int main()
{
    iostream::sync_with_stdio(0);
    cin.tie(0);
    be();
    //for (int i=1; i<=n; i++) cout<<a[i].szam<<":"<<a[i].x<<"-"<<a[i].y<<endl;
    int i=1;
    while (a[i].x==1 && i<n+2) i++;
    if(i==n+2) cout<<-1;
    else {
        M[0]=a[i-1].szam;
        h=a[i-1].y;
        s++;
        while (h!=m) {
            if (i>n) {
                cout<<-1;
                return 0;
            }
            int c=0;
            for(int t=i; t<=n; t++) {
                if (a[t].x<=h && M[s]<a[t].y) {
                    M[s]=a[t].szam;
                    c=t;
                }
            }
            h=a[c].y;
            s++;
            i=c+1;
        }
        cout<<s-1<<endl;
        for (int j=0; j<s; j++) cout<<M[j]<<" ";
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base23/50
1Accepted0/01ms316 KiB
2Wrong answer0/010ms316 KiB
3Accepted1/11ms316 KiB
4Time limit exceeded0/1280ms316 KiB
5Wrong answer0/21ms316 KiB
6Accepted2/21ms316 KiB
7Accepted2/21ms316 KiB
8Time limit exceeded0/2300ms316 KiB
9Wrong answer0/22ms532 KiB
10Wrong answer0/22ms500 KiB
11Wrong answer0/23ms476 KiB
12Time limit exceeded0/2300ms316 KiB
13Accepted2/21ms316 KiB
14Accepted2/22ms316 KiB
15Accepted2/23ms316 KiB
16Wrong answer0/24ms440 KiB
17Wrong answer0/27ms316 KiB
18Wrong answer0/28ms316 KiB
19Wrong answer0/28ms540 KiB
20Time limit exceeded0/2284ms724 KiB
21Wrong answer0/210ms316 KiB
22Wrong answer0/29ms316 KiB
23Accepted2/24ms316 KiB
24Accepted2/24ms316 KiB
25Accepted2/24ms316 KiB
26Accepted2/24ms508 KiB
27Accepted2/24ms320 KiB
28Accepted2/24ms316 KiB