제출 #575525

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

molecules

#include<bits/stdc++.h>
#include "molecules.h"
using namespace std;

bool construct(vector<int>& range, vector<pair<int,int> >& a, vector<int>& sol, int left, int right){
    int n=a.size();
    int x=0;
    int i=0;

    reverse(range.begin(), range.end()); //=> aufsteigend
    range.push_back(INT_MAX);
    reverse(a.begin(), a.end()); //=> aufsteigend
    /*for(auto e: a){
        cout << e.first << " " << e.second << "\n";
    }
    cout << "=====\n";
    for(auto e: range){
        cout << e << "\n";
    }
    cout << ":::::::::::::::::::::::::\n";*/
    for(int j=0; j<n; j++){
        if(range[j+1]<x) continue;

        int l=range[j];
        while(i<=j && x<l+(a[j].first-a[i].first)){
            //cout << j << " " << i << "\n";
            i++;
        }
        if(i>j) return false;
        //cout << x << " " << range[j] <<  " " << a[i].first << "\n";
        sol.push_back(a[i].second);
        x+=a[i].first;
        i++;
    }
    if(x<left || right<x) return false;
    return true;
}

vector<int> find_subset(int l, int r, vector<int> a){
    int n=a.size();
    vector<pair<int,int> > b(n);
    for(int i=0; i<n; i++){
        b[i]={a[i], i};
    }
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());

    vector<int> range(1, l);
    for(int i=0; i<n; i++){
        range.push_back(range[i]-b[i].first);
    }

    /*for(auto e: range){
        cout << e.first << " " << e.second << "\n";
    }*/
    
    vector<int> sol;
    if(construct(range, b, sol, l, r)){
        return sol;
    }
    return {};
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, l, r;
    cin >> n >> l >> r;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    vector<int> sol=find_subset(l, r, a);
    for(auto e: sol){
        cout << e << " ";
    }
    cout << "\n";
}*/

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