139842025-01-09 13:58:23BencuA lehető legkevesebb átszállás (50 pont)cpp17Hibás válasz 23/50300ms516 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()
{
    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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base23/50
1Elfogadva0/01ms316 KiB
2Hibás válasz0/014ms316 KiB
3Elfogadva1/11ms316 KiB
4Időlimit túllépés0/1279ms316 KiB
5Hibás válasz0/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/22ms316 KiB
8Időlimit túllépés0/2298ms316 KiB
9Hibás válasz0/23ms316 KiB
10Hibás válasz0/23ms316 KiB
11Hibás válasz0/24ms316 KiB
12Időlimit túllépés0/2300ms316 KiB
13Elfogadva2/22ms316 KiB
14Elfogadva2/23ms316 KiB
15Elfogadva2/24ms316 KiB
16Hibás válasz0/26ms316 KiB
17Hibás válasz0/29ms316 KiB
18Hibás válasz0/210ms316 KiB
19Hibás válasz0/213ms316 KiB
20Időlimit túllépés0/2300ms316 KiB
21Hibás válasz0/214ms508 KiB
22Hibás válasz0/214ms516 KiB
23Elfogadva2/28ms504 KiB
24Elfogadva2/28ms468 KiB
25Elfogadva2/28ms316 KiB
26Elfogadva2/28ms428 KiB
27Elfogadva2/28ms316 KiB
28Elfogadva2/28ms400 KiB