제출 #414782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414782		MeGustaElArroz23	Detecting Molecules (IOI16_molecules)	C++14	0 / 100	1 ms	332 KiB

molecules

#include <cstdio>
#include <vector>
#include <cassert>

#include "molecules.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;

void debug(vi v){
    for (auto x:v) cerr << x << ' ';
    cerr << '\n';
}
void debug(vii v){
    for (auto x:v) cerr << x.first <<' '<< x.second << '\n';
    cerr << '\n';
}

vector<int> find_subset(int l, int u, vector<int> w) {
    //cerr<<1;
    int n=w.size();
    vii v(n);
    //cerr<<4;
    for (int i=0;i<n;i++) v[i]=pii{w[i],i};
    //cerr<<3;
    sort(v.begin(),v.end());
    vii pref(n+1);
    pref[0]=pii{0,0};
    //cerr<<2;
    for (int i=1;i<=n;i++){
        pref[i].first=pref[i-1].first+v[i-1].first;
        pref[i].second=pref[i-1].second+v[n-i].first;
    }
    //cerr<<0;
    //debug(pref);
    for (int i=1;i<=n;i++){
        if ((l>=pref[i].first and l<=pref[i].second) or (u>=pref[i].first and u<=pref[i].second) or (l<=pref[i].first and u>=pref[i].second)){
            //cerr<<i;
            vi sol(i);
            for (int j=0;j<i;j++) sol[j]=j;
            ll suma=pref[i].first;
            int counter=0;
            while(suma<u){
                //debug(sol);
                //cerr << suma << '\n';
                suma-=v[counter].first;
                suma+=v[n-counter-1].first;
                sol[counter]=n-counter-1;
                counter++;

            }
            debug(sol);
            cerr << suma << '\n';
            //debug(sol);
            //cerr<<0;
            for (int j=0;j<i;j++) sol[j]=v[sol[j]].second;
            //debug(sol);
            //cerr<<1;
            sort(sol.begin(),sol.end());
            vector<int> solu(i);
            for (int j=0;j<i;j++) solu[j]=sol[j];
            return solu;
        }
    }
    return vector<int>(0);
}

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