oj.uz

Submission #642182

# Submission time Handle Problem Language Result Execution time Memory
642182 2022-09-18T15:50:39 Z Ahmad_Hasan Sticks (POI11_pat) C++17
100 / 100
 524 ms 14884 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Oczekiwano NIE

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Oczekiwano NIE
2 Correct 16 ms 972 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Oczekiwano NIE
2 Correct 18 ms 1304 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Oczekiwano NIE
2 Correct 37 ms 2164 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 904 KB Oczekiwano NIE
2 Correct 52 ms 3424 KB Output is correct
3 Correct 124 ms 2412 KB Oczekiwano NIE

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 2112 KB Oczekiwano NIE
2 Correct 104 ms 6040 KB Output is correct
3 Correct 206 ms 3680 KB Oczekiwano NIE

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 6888 KB Output is correct
2 Correct 163 ms 6296 KB Output is correct
3 Correct 226 ms 3760 KB Oczekiwano NIE

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 6864 KB Output is correct
2 Correct 341 ms 6184 KB Output is correct
3 Correct 328 ms 6284 KB Oczekiwano NIE

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 12756 KB Output is correct
2 Correct 215 ms 8624 KB Output is correct
3 Correct 423 ms 8968 KB Oczekiwano NIE

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 12724 KB Output is correct
2 Correct 275 ms 9972 KB Output is correct
3 Correct 524 ms 14884 KB Oczekiwano NIE