이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std; vector < pair < pair <double, int>, pair <double, double> > > k; map <double, int> saz; vector < pair <double, int> > qi; map <int, double> ob; double min_w;
vector < pair < int, int > > sol;
const int OFF = (1 << 19);
double tour[2*OFF];
void update(int x, double v) {
x+=OFF;
tour[x]=v;
x/=2;
while (x) {
tour[x]=tour[x*2]+tour[x*2+1];
x/=2;
}
return;
}
pair<int, double> query(int lo=0, int hi=OFF-1, int x=1, double now=0) {
if (lo==hi) return {x-OFF, now};
int mid=(lo+hi)/2;
double le=tour [x*2];
double de=tour [x*2+1];
if (le+now>min_w) return query(lo, mid, x*2, now);
else return query(mid+1, hi, x*2+1, le+now);
}
int fen[OFF+10];
void dodaj(int a, int v){
for (a; a<OFF+10; a+= a & -a) fen[a]+=v;
}
int ispis(int a){
if (a==0 || a==-1) return 0;
int izlaz=0;
for (a; a>0; a-= a & -a) izlaz+=fen[a];
return izlaz;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; double w; cin >> n >> w;
for (int i=0; i<n; i++){
double s, q; cin >> s >> q;
double x=s/q;
k.push_back({{x, i}, {s, q}});
qi.push_back({q, i});
}
sort (qi.begin (), qi.end ());
sort (k.begin (), k.end (), [](pair < pair <double, int>, pair <double, double> > a, pair < pair <double, int>, pair <double, double> > b){
return a.second.first*b.second.second<b.second.first*a.second.second;
});
int ind=1;
for (int i=0; i<qi.size(); i++){
//cout << qi [i] << endl;
saz [qi[i].second]=ind; ind++;
}
int max_ans=-1, res; double platit=0;
for (int i=0; i<n; i++){
double x=k[i].first.first;
min_w=w/x;
int ind=saz [k[i].first.second];
//cout << x << " " << min_w << " " << ind << " " << k[i].first.second << endl;
double val=k[i].second.second;
dodaj (ind, 1);
update (ind, val);
int gr=query ().first;
double zb=query ().second;
//cout << zb*x << endl;
if (ispis (gr-1)>max_ans || (ispis (gr-1)==max_ans && zb*x<platit)){
max_ans=ispis (gr-1); platit=zb*x; res=i;
}
}
//cout << res << endl;
for (int i=0; i<res+1; i++){
int ind1=k[i].first.second;
sol.push_back((make_pair(saz[k[i].first.second], ind1)));
}
sort (sol.begin(), sol.end());
cout << max_ans << endl;
for (int i=0; i<max_ans; i++) cout << sol [i].second+1 << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
hiring.cpp: In function 'std::pair<int, double> query(int, int, int, double)':
hiring.cpp:20:12: warning: unused variable 'de' [-Wunused-variable]
20 | double de=tour [x*2+1];
| ^~
hiring.cpp: In function 'void dodaj(int, int)':
hiring.cpp:26:7: warning: statement has no effect [-Wunused-value]
26 | for (a; a<OFF+10; a+= a & -a) fen[a]+=v;
| ^
hiring.cpp: In function 'int ispis(int)':
hiring.cpp:31:7: warning: statement has no effect [-Wunused-value]
31 | for (a; a>0; a-= a & -a) izlaz+=fen[a];
| ^
hiring.cpp: In function 'int main()':
hiring.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i=0; i<qi.size(); i++){
| ~^~~~~~~~~~
hiring.cpp:70:17: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
70 | for (int i=0; i<res+1; i++){
| ~^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |