Submission #591609

#	Time	Username	Problem	Language	Result	Execution time	Memory
591609		mosiashvililuka	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	69 ms	7884 KiB

molecules

#include<bits/stdc++.h>
#include "molecules.h"
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[200009],l,r,jm,I,X;
vector <int> vv;
pair <long long, long long> p[200009];
void DO(){
    vector <int> qw;
    for(int h=0; h<vv.size(); h++){
        qw.push_back(p[vv[h]].second-1);
    }
    sort(qw.begin(),qw.end());
    vv=qw;
}
vector<int> find_subset(int Ll, int Uu, std::vector<int> Ww) {
    a=Ww.size();
    l=Ll;r=Uu;
    for(i=1; i<=a; i++) f[i]=Ww[i-1];
    for(i=1; i<=a; i++){
        p[i]={f[i],i};
    }
    sort(p+1,p+a+1);
    sort(f+1,f+a+1);
    jm=0;
    for(i=a; i>=1; i--){
        jm+=f[i];
        if(jm<l) continue;
        if(jm<=r){
            for(j=i; j<=a; j++) vv.push_back(j);
            DO();
            return vv;
        }
        if(jm>r) break;
    }
    if(jm<l){
        DO();
        return vv;
    }
    I=i;X=a-i+1;
    zx=0;
    for(i=1; i<=X; i++){
        zx+=f[i];
    }
    if(zx>r){
        DO();
        return vv;
    }
    for(i=I; i<=a; i++) vv.push_back(i);
    ii=0;jj=0;
    while(1){
        if(vv[ii]==jj+1){
            ii++;
            jj++;
        }
        if(ii==vv.size()) break;
        jm-=f[vv[ii]];
        vv[ii]=jj+1;
        jm+=f[vv[ii]];
        if(jm>=l&&jm<=r){
            DO();
            return vv;
        }
    }
    cout<<"ERORI";
}

Compilation message (stderr)

molecules.cpp: In function 'void DO()':
molecules.cpp:9:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for(int h=0; h<vv.size(); h++){
      |                  ~^~~~~~~~~~
molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:55:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if(ii==vv.size()) break;
      |            ~~^~~~~~~~~~~
molecules.cpp:64:11: warning: control reaches end of non-void function [-Wreturn-type]
   64 |     cout<<"ERORI";
      |           ^~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31