Submission #210219

#	Time	Username	Problem	Language	Result	Execution time	Memory
210219		sealnot123	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	88 ms	5624 KiB

molecules

#include "molecules.h"
//#include "grader.cpp"

#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;
const int N=200007;

VI ans, nn, w;
int n;

VI find_subset(int l, int r, VI W) {
    int i,j,k,a,b,c,d;
    w = W;
    n = SZ(w);
    nn.resize(n);
    iota(all(nn),0);
    sort(all(nn), [](int a, int b){ return w[a] < w[b]; });
    //for(i=0;i<n;i++) printf("%d ",nn[i]);
    //printf("\n");
    sort(all(w));
    LL sum = 0;
    for(int e: w) sum += e;
    if(sum < l) return ans;
	if(w[0] > r) return ans;
    LL L = l-sum, R = r-sum;
    LL now = 0;
    int last = n-1;
    for(i=n-1;i>=0;i--){
        //printf("%lld %lld\n",L,R);
        if(L <= now && now <= R){
            while(R + w[i] < now + w[last]) last--;
            ans.pb(nn[last]);
            now += w[last];
            last--;
        }
        R += w[i], L += w[n-i-1];
    }
	return ans;
}
/*
3 6 9
5 5 5

4 14 15
5 5 6 6

4 15 17
6 8 8 7

4 10 20
15 17 16 18
*/

Compilation message (stderr)

molecules.cpp: In function 'VI find_subset(int, int, VI)':
molecules.cpp:26:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j,k,a,b,c,d;
           ^
molecules.cpp:26:13: warning: unused variable 'k' [-Wunused-variable]
     int i,j,k,a,b,c,d;
             ^
molecules.cpp:26:15: warning: unused variable 'a' [-Wunused-variable]
     int i,j,k,a,b,c,d;
               ^
molecules.cpp:26:17: warning: unused variable 'b' [-Wunused-variable]
     int i,j,k,a,b,c,d;
                 ^
molecules.cpp:26:19: warning: unused variable 'c' [-Wunused-variable]
     int i,j,k,a,b,c,d;
                   ^
molecules.cpp:26:21: warning: unused variable 'd' [-Wunused-variable]
     int i,j,k,a,b,c,d;
                     ^

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