제출 #1333451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1333451		candi_ositos	새로운 문제 (POI11_pat)	C++20	68 / 100	364 ms	131072 KiB

pat

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin>>n;
    vector <pair <int, int> > fp;
    vector <vector <int> > ps(n);
    for(int i=0; i<n; ++i){
        int aux;
        cin>>aux;
        for(int j=0; j<aux; ++j){
            int a;
            cin>>a;
            fp.push_back({a, i});
        }
    }
    m=fp.size();
    ps.assign(n, vector <int> (m, 0));
    sort(fp.begin(), fp.end());
    ps[fp[0].second][0]=1;
    for(int i=1; i<m; ++i){
        for(int j=0; j<n; ++j){
            ps[j][j]=ps[j][i-1];
        }
        ++ps[fp[i].second][i];
    }
    while(m>2){
        if(fp[m-1].second==fp[m-2].second){
            fp.pop_back();
            --m;
            continue;
        }
        if(fp[m-3].first<=fp[m-1].first-fp[m-2].first){
            fp.pop_back();
            --m;
            continue;
        }
        int li=0, ri=m-3;
        while(li<ri){
            int aux=(li+ri)/2;
            if(fp[aux].first<=fp[m-1].first-fp[m-2].first){
                li=aux+1;
                continue;
            }
            ri=aux;
        }
        if(fp[li].second!=fp[m-1].second && fp[li].second!=fp[m-2].second){
            cout<<fp[li].second+1<<" "<<fp[li].first<<" "<<fp[m-2].second+1<<" "<<fp[m-2].first<<" "<<fp[m-1].second+1<<" "<<fp[m-1].first<<"\n";
            return 0;
        }
        for(int i=0; i<n; ++i){
            if(i==fp[m-1].second || i==fp[m-2].second){
                continue;
            }
            if(ps[i][m-3]-ps[i][li]>0){
                for(int j=li+1; j<m-2; ++j){
                    if(fp[j].second!=fp[m-1].second && fp[j].second!=fp[m-2].second){
                        cout<<fp[j].second+1<<" "<<fp[j].first<<" "<<fp[m-2].second+1<<" "<<fp[m-2].first<<" "<<fp[m-1].second+1<<" "<<fp[m-1].first<<"\n";
                        return 0;
                    }
                }
            }
        }
        --m;
        fp.pop_back();
    }
    cout<<"NIE\n";
    return 0;
}

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