Submission #642182

#	Time	Username	Problem	Language	Result	Execution time	Memory
642182		Ahmad_Hasan	Sticks (POI11_pat)	C++17	100 / 100	524 ms	14884 KiB

pat

#include<bits/stdc++.h>
using namespace std;


int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);

    int k;
    cin>>k;
    vector<vector<int> >clrs(k+5);
    vector<pair<int,int> >vps;
    for(int i=1;i<=k;i++){
        int n;
        cin>>n;
        clrs[i]=vector<int>(n);
        for(int j=0;j<n;j++){cin>>clrs[i][j];vps.push_back({clrs[i][j],i});}
        sort(clrs[i].begin(),clrs[i].end());
    }

    sort(vps.begin(),vps.end());

    vector<pair<int,int> >ans;
    for(int i=0;i<vps.size() && ans.size()==0;i++){
        for(int j=1;j<=k && ans.size()==0;j++){
            if(j==vps[i].second)continue;
            int mx=upper_bound(clrs[j].begin(),clrs[j].end(),vps[i].first)-clrs[j].begin();

            mx--;
            if(mx<0)continue;
            mx=clrs[j][mx];
            int ttl=lower_bound(vps.begin(),vps.end(),make_pair(mx+vps[i].first,-1))-lower_bound(vps.begin(),vps.end(),make_pair(vps[i].first,-1));
            int sum=0;
            sum+=lower_bound(clrs[j].begin(),clrs[j].end(),mx+vps[i].first)-lower_bound(clrs[j].begin(),clrs[j].end(),vps[i].first);
            sum+=lower_bound(clrs[vps[i].second].begin(),clrs[vps[i].second].end(),mx+vps[i].first)-lower_bound(clrs[vps[i].second].begin(),clrs[vps[i].second].end(),vps[i].first);
            if(ttl>sum){
                ans.push_back({mx,j});
                ans.push_back(vps[i]);
                for(int ii=lower_bound(vps.begin(),vps.end(),make_pair(vps[i].first,-1))-vps.begin();ii<vps.size();ii++){
                    if(vps[ii].second!=j&&vps[ii].second!=vps[i].second&&vps[ii].first<mx+vps[i].first){
                        ans.push_back(vps[ii]);
                        break;
                    }
                }
                break;
            }
        }
    }
    if(ans.size()){
        for(int i=0;i<3;i++){
            cout<<ans[i].second<<' '<<ans[i].first<<' ';
        }
    }else{
        cout<<"NIE";
    }



    return 0;
}

Compilation message (stderr)

pat.cpp: In function 'int32_t main()':
pat.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<vps.size() && ans.size()==0;i++){
      |                 ~^~~~~~~~~~~
pat.cpp:39:104: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |                 for(int ii=lower_bound(vps.begin(),vps.end(),make_pair(vps[i].first,-1))-vps.begin();ii<vps.size();ii++){
      |                                                                                                      ~~^~~~~~~~~~~

• 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: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8
• Subtask 13: 8 / 8