제출 #1317941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317941		_unknown_2010	Detecting Molecules (IOI16_molecules)	C++20	46 / 100	669 ms	2092 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector
// #define int long long
#define all(x) (x).begin(), (x).end()
mt19937 rng(363636);
namespace sub4 {
    bool check(int n, int l, int u) {
        return (n <= 10000 && u <= 500000);
    }
    vector<int> find_subset(int l, int u, vector<int> w) {
        vi<int> dp(2e5), ind(2e5);
        dp[0]=1;
        for(int i=0; i<w.size(); i++){
            for(int j=1e5; j>=w[i]; j--){
                if(dp[j])continue;
                if(dp[j-w[i]])dp[j]=w[i], ind[j]=i;
            }
        }
        vi<int> ans;
        for(int i=l; i<=u; i++){
            if(dp[i]){
                int x=i;
                while(x!=0){
                    ans.push_back(ind[x]);
                    x-=dp[x];
                }
                break;
            }
        }
        return ans;
    }
}

namespace sub5 {
    vector<int> find_subset(int l, int u, vector<int> w) {
        int n=w.size(), thre=36;
        vi<pair<int,int>> v;
        for(int i=0; i<w.size(); i++){
            v.push_back({w[i], i});
        }
        sort(all(v));
        if(v[0].first>=l && v[0].first<=u){
            return vi<int>{0};
        }
        if(v[n-1].first>=l && v[n-1].first<=u){
            return vi<int>{n-1};
        }
        if(v[0].first>u){
            return vi<int> {};
        }
        for(int _=0; _<1000; _++){
            for(int i=0; i<n; i+=thre){
                int r=min(n-1, i+thre-1);
                shuffle(v.begin()+i, v.begin()+r+1, rng);
            }
            int sum=0;
            vi<int> ans;
            for(int i=0; i<n; i++){
                sum+=v[i].first;
                ans.push_back(v[i].second);
                if(sum>=l && sum<=u){
                    return ans;
                }
            }
        }
        return vi<int>{};
    }
}

vector<int> find_subset(int l, int u, vector<int> w) {
    int n = w.size();
    if (sub4::check(n, l, u)) return sub4::find_subset(l, u, w);
    return sub5::find_subset(l, u, w);
}

컴파일 시 표준 에러 (stderr) 메시지

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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