제출 #501454

#제출 시각아이디문제언어결과실행 시간메모리
501454MurotYDetecting Molecules (IOI16_molecules)C++14
0 / 100
1 ms204 KiB
#include <bits/stdc++.h> #define ll long long #define ff first #define ss second #include "molecules.h" using namespace std; std::vector<int> find_subset(int l, int u, std::vector<int> w) { vector <pair <ll,ll> > a(w.size()+1); map <ll,ll> mp; ll sum=0; int mn=1e9, mx=0; for (int i=0;i<w.size();i++) a[i+1].ff=w[i], a[i].ss=i,sum+=w[i], mp[w[i]]++, mx=max(mx, w[i]), mn=min(mn, w[i]); int n=w.size()+1; sort(a.begin()+1, a.end()); vector <ll> dp(sum+1, 0); vector <ll> v[sum+1]; dp[0]=1; for (int i=1;i<=n;i++) v[a[i].ff].push_back(a[i].ss); for (int i=1;i<=n;i++){ for (int j=sum;j>=0;j--){ if (a[i].ff+j <= sum and dp[a[i].ff+j] == 0){ dp[a[i].ff+j] |= dp[j]; if (dp[a[i].ff+j] and mp[a[i].ff+j] == 0) { for (auto it:v[j]) v[j+a[i].ff].push_back(it); if (j != 0) for (auto it:v[a[i].ff]) v[j+a[i].ff].push_back(it); } } } } ll jv=-1, res=1e9; for (int i=l;i<=sum;i++){ if (i > u) break; if (dp[i]){ if (res > v[i].size()){ res=v[i].size(); jv=i; } } } vector <int> ans; if (jv == -1 or mx-mn > u-l); else for (auto l:v[jv]) ans.push_back(l); return ans; }

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

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i=0;i<w.size();i++) a[i+1].ff=w[i], a[i].ss=i,sum+=w[i], mp[w[i]]++,
      |                  ~^~~~~~~~~
molecules.cpp:37:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if (res > v[i].size()){
      |             ~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...