Submission #165434

#	Time	Username	Problem	Language	Result	Execution time	Memory
165434		Segtree	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	164 ms	21436 KiB

molecules

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include"molecules.h"
using namespace std;
typedef long long ll;
vector<int> ans;
unordered_map<int,vector<int> >mas;
void exch(){
    for(int i=0;i<ans.size();i++){
	ll x=ans[i];
	ans[i]=mas[x].back();
	mas[x].pop_back();
    }
}
vector<int> find_subset(int l,int r,vector<int> w){
    int n=w.size();
    for(int i=0;i<n;i++){
	mas[w[i]].push_back(i);
    }
    sort(w.begin(),w.end());
    ll suml=0,sumr=0,x=-1;
    for(int i=0;i<n;i++){
	suml+=w[i];
	sumr+=w[n-1-i];
	if(suml<=r&&l<=sumr){
	    x=i+1;
	    break;
	}
    }
    if(x==-1)return ans;
    for(int i=0;i<x;i++)ans.push_back(w[i]);
    if(l<=suml&&suml<=r){
	exch();
	return ans;
    }
    for(int i=x-1;i>=0;i--){
	suml-=ans[i];
	suml+=w[n-x+i];
	ans[i]=w[n-x+i];
	if(l<=suml&&suml<=r){
	    exch();
	    return ans;
	}
    }
    cout<<1/0<<endl;
    return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'void exch()':
molecules.cpp:11:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ans.size();i++){
                 ~^~~~~~~~~~~
molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:47:12: warning: division by zero [-Wdiv-by-zero]
     cout<<1/0<<endl;
           ~^~

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