oj.uz

Submission #642176

# Submission time Handle Problem Language Result Execution time Memory
642176 2022-09-18T15:47:23 Z Ahmad_Hasan Sticks (POI11_pat) C++17
84 / 100
 298 ms 33388 KB 
#include<bits/stdc++.h>
#define int long long
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,-1ll))-lower_bound(vps.begin(),vps.end(),make_pair(vps[i].first,-1ll));
            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,-1ll))-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:25:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<vps.size() && ans.size()==0;i++){
      |                 ~^~~~~~~~~~~
pat.cpp:40:106: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                 for(int ii=lower_bound(vps.begin(),vps.end(),make_pair(vps[i].first,-1ll))-vps.begin();ii<vps.size();ii++){
      |                                                                                                        ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 9 ms 1324 KB Output is correct

Subtask #6
8.0 / 8.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 596 KB Oczekiwano NIE
2 Correct 29 ms 3792 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1148 KB Oczekiwano NIE
2 Correct 49 ms 6852 KB Output is correct
3 Correct 113 ms 3908 KB Oczekiwano NIE

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3480 KB Oczekiwano NIE
2 Correct 103 ms 12844 KB Output is correct
3 Correct 155 ms 6848 KB Oczekiwano NIE

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 16816 KB Output is correct
2 Correct 100 ms 13468 KB Output is correct
3 Correct 201 ms 7664 KB Oczekiwano NIE

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 16816 KB Output is correct
2 Correct 130 ms 13156 KB Output is correct
3 Correct 298 ms 12964 KB Oczekiwano NIE

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 267 ms 33388 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 268 ms 33328 KB Memory limit exceeded
2 Halted 0 ms 0 KB -