Advertisement
sonprao

G. ACMMienNam

Oct 20th, 2019
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(i=a;i<=b;i++)
  3. using namespace std;
  4. pair<long long,long long> a[1000000];
  5. vector<long long > b;
  6. vector<long long > RES;
  7. map<long long,long long> cnt;
  8. map<long long,long long> M;
  9. map<long long,long long>::iterator it;
  10. long long i,n,res,S,x,y,h,k,res1,res2,res3,res4,min1,min2;
  11. long long binsearch_left(vector<long long> A  ,long long L,long long R ,long long val)
  12. {
  13.  
  14.     while (L < R)
  15.       {
  16.         long long m = floor((L+R)/2);
  17.         if (A[m]<val) L=m+1;
  18.         else R=m;
  19.       }
  20.     return L;
  21. }
  22. int main(){
  23.     cin>>n>>S;
  24.     FOR(i,1,n) {cin>>a[i].first; a[i].second=i;}
  25.     sort(a+1,a+1+n);
  26.     FOR(i,1,n) {
  27.         if (cnt.find(a[i].first)==cnt.end())cnt[a[i].first]=1; else cnt[a[i].first]++;
  28.         if (M.find(a[i].first)==M.end()) M[a[i].first]=a[i].second;
  29.         else if (a[i].second< M[a[i].first]) M[a[i].first]=a[i].second;
  30.     }
  31.     for(it=cnt.begin();it!=cnt.end();it++)
  32.         if ((it->second)>1)
  33.             b.push_back(it->first);
  34.     sort(b.begin(),b.end());
  35.     //if (b[i].first>=4) res=MAX(res,b[i].first*b[i].first);
  36.     // FOR(i,0,b.size()-1)
  37.    //  cout<<b[i]<<" ";
  38.     // cout<<endl<<endl;
  39.     //FOR(i,0,b.size()-1)
  40.     //cout<<b[i]<<" "<<binsearch_left(b,0,b.size()-1,S/b[i])<<" "<<endl;
  41.     //cout<<endl;
  42.     res=0;
  43.     if (b.size()==0) {cout<<"-1"; return 0;}
  44.     FOR(i,0,b.size()-1)
  45.     {
  46.         x=S/b[i];
  47.         y=binsearch_left(b,0,b.size()-1,x);
  48.         if (y!=i)
  49.         {
  50.            if ((b[i]*b[y]>res) && (b[i]*b[y]<=S))
  51.            {    res=b[i]*b[y];
  52.                 h=b[i];
  53.                 k=b[y];
  54.             }
  55.             else
  56.             if(((b[i]*b[y])==res) && (b[i]*b[y]<=S))
  57.                 {
  58.                     min1=min(M[h],M[k]);
  59.                     min2=min(M[b[i]],M[b[y]]);
  60.                     if (min1>min2) {h=b[i]; k=b[y];}
  61.                 }
  62.         }
  63.         else if ((cnt[b[i]]>3)&&(b[i]*b[y]<=S))
  64.         if (b[i]*b[y]>res)
  65.            {res=b[i]*b[y];
  66.             h=b[i];
  67.             k=b[y];}
  68.             else if ((b[i]*b[y])==res)
  69.         {
  70.             min1=min(M[h],M[k]);
  71.             min2=min(M[b[i]],M[b[y]]);
  72.             if (min1>min2) {h=b[i]; k=b[y];}
  73.         }
  74.     }
  75.     if (res==0) {cout<<"-1"; return 0;}
  76.     //cout<<res<<" "<<h<<" "<<k<<endl;
  77.     FOR(i,1,n) if (a[i].first==h){res1=i; RES.push_back(a[i].second); break;}
  78.     FOR(i,res1+1,n) if (a[i].first==h){res2=i; RES.push_back(a[i].second); break;}
  79.     FOR(i,1,n) if (a[i].first==k) {res3=i;  RES.push_back(a[i].second); break;}
  80.     FOR(i,res3+1,n) if (a[i].first==k) {res4=i;     RES.push_back(a[i].second); break;}
  81.     sort(RES.begin(),RES.end());
  82.     FOR(i,0,RES.size()-1) cout<<RES[i]<<" ";
  83.     return 0;
  84. }
  85. /*
  86. 14 19
  87. 3 4 2 6 5 9 3 9 5 4 6 2 10 10
  88. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement