이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
const int MAXQ = 2e4 + 10;
typedef long ll;
#define esq(x) x << 1
#define dir(x) (x<<1) | 1
#define mid(x,y,t) ((x+y)>>1) + t
#define debug(args...) //debug(stderr, args)
int MAX = 2e4 + 10;
bool sorttwo;
struct worker{
int id;
double q, s;
bool operator < (worker w) const{
return s/q < w.s/w.q;
}
} workers[MAXN];
struct nodeseg{
ll qaqui;
int act;
bool f;
nodeseg(ll _q = 0, int _a = 0, bool _f = 0){
qaqui = _q;
act = _a;
f = _f;
}
nodeseg operator + (nodeseg b){
if(f && b.f) return nodeseg(0,0,1);
if(f) return b;
if(b.f) return *this;
nodeseg ans = nodeseg(qaqui + b.qaqui, act + b.act, 0);
return ans;
}
} seg[4*MAXQ];
void update(int node, int x, int y, int q){
debug(stderr, "oiu\n");
if(x > q || y < q) return;
if(x == y){
seg[node].act++;
seg[node].qaqui += q;
return;
}
update(esq(node), x, mid(x,y,0), q);
update(dir(node), mid(x,y,1), y, q);
seg[node] = seg[esq(node)] + seg[dir(node)];
}
nodeseg query(int node, int x, int y, int l, int r){
debug(stderr, "oiq\n");
if(x > r || y < l) return nodeseg(0,0,1);
if(x >= l && y <= r) return seg[node];
nodeseg e = query(esq(node), x, mid(x,y,0), l, r);
nodeseg d = query(dir(node), mid(x,y,1), y, l, r);
return e + d;
}
int bb(int node, int x, int y, ll q){
debug(stderr, "oi\n");
debug("BB %lld\n", q);
if(x == y) return x;
if(seg[esq(node)].qaqui >= q){
return bb(esq(node), x, mid(x,y,0), q);
}
return bb(dir(node), mid(x,y,1), y, q - seg[esq(node)].qaqui);
}
bool comp(worker i, worker j){
return i.q < j.q;
}
double w;
int n;
int main(){
scanf("%d %lf", &n, &w);
for(int i = 1; i <= n; i++){
scanf("%lf %lf", &workers[i].s, &workers[i].q );
workers[i].q = (int)workers[i].q;
workers[i].id = i;
}
sort(workers + 1, workers + 1 + n);
double kfd;
int qtd = 0;
double tots = 1e18;
for(int i = 1; i <= n; i++){
double k = workers[i].s/workers[i].q;
double aq = w/k;
int tot = 0;
double totq = 0;
debug("%d %lf %lf\n", workers[i].id, k, aq);
debug(stderr, "%d afs\n", i);
debug(stderr, "%lf", workers[i].q);
update(1,1,MAX,workers[i].q);
if(seg[1].qaqui <= aq){
tot = seg[1].act;
totq = seg[1].qaqui;
}else{
int id = bb(1,1,MAX,(int)aq) - 1;
tot = query(1,1,MAX,1,id).act;
totq = query(1,1,MAX,1,id).qaqui;
}
if(tot == qtd){
debug("T: %d\n", tot);
if(tots > totq*k ){
kfd = k;
tots =totq*k;
}
}
if(tot > qtd){
debug("T: %d\n", tot);
kfd = k;
qtd = tot;
tots = totq*k;
}
}
vector<int> ans;
sorttwo = 1;
sort(workers + 1, workers + 1 + n, comp);
double aq = 0;
for(int j = 1; j <= n; j++){
if(workers[j].q* kfd < workers[j].s) continue;
aq += kfd*workers[j].q;
if(aq > w){
break;
}
ans.push_back(workers[j].id);
}
printf("%d\n",(int)ans.size() );
for(int i : ans) printf("%d\n", i);
}
컴파일 시 표준 에러 (stderr) 메시지
hiring.cpp: In function 'int main()':
hiring.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d %lf", &n, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~
hiring.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%lf %lf", &workers[i].s, &workers[i].q );
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hiring.cpp:133:18: warning: 'kfd' may be used uninitialized in this function [-Wmaybe-uninitialized]
133 | if(workers[j].q* kfd < workers[j].s) continue;
| ~~~~~~~~~~~~^~~~~
# | 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... |