oj.uz

답안 #866422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
866422 2023-10-26T06:09:42 Z HuyQuang_re_Zero Hiring (IOI09_hiring) C++14
3 / 100
 179 ms 14980 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
struct pt { ll cnt,sum; };
pt operator + (pt a,pt b) { return { a.cnt+b.cnt,a.sum+b.sum }; }
struct worker { ll s,q,pos; } a[N];
ll n,i,w,u,res,top,bot;
struct Interval_Tree
{
    pt st[100005];
    void update(int id,int l,int r,int u)
    {
        if(u<l || u>r) return ;
        if(l==r) { st[id].cnt++; st[id].sum+=u; return ; }
        int mid=(l+r)>>1;
        update(id*2,l,mid,u); update(id*2+1,mid+1,r,u);
        st[id]=st[id*2]+st[id*2+1];
    }
    pt Find(int id,int l,int r,ll k)
    {
        if(l==r) return { min(k/l,st[id].cnt),l*min(k/l,st[id].cnt) };
        int mid=(l+r)>>1;
        if(k<st[id*2].sum) return Find(id*2,l,mid,k);
        return st[id*2]+Find(id*2+1,mid+1,r,k-st[id*2].sum);
    }
} IT;
int main()
{
 //  freopen("hiring.inp","r",stdin);
   // freopen("hiring.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>w;
    for(i=1;i<=n;i++) cin>>a[i].s>>a[i].q,a[i].pos=i;
    sort(a+1,a+n+1,[&](worker a,worker b){ return a.s*b.q<a.q*b.s; });
    for(i=1;i<=n;i++)
    {
        IT.update(1,1,20000,a[i].q);
        pt x=IT.Find(1,1,20000,w*a[i].q/a[i].s);
        if(res<x.cnt || (res==x.cnt && top*a[i].q>bot*a[i].s*x.sum));
        {
            res=x.cnt;
            top=a[i].s*x.sum; bot=a[i].q;
            u=i;
        }
    }
    cout<<res<<'\n';
    sort(a+1,a+u+1,[&](worker a,worker b){ return a.q<b.q; });
    for(i=1;i<=res;i++) cout<<a[i].pos<<'\n';
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:53:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   53 |         if(res<x.cnt || (res==x.cnt && top*a[i].q>bot*a[i].s*x.sum));
      |         ^~
hiring.cpp:54:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   54 |         {
      |         ^

Subtask #1
3.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Partially correct 0 ms 2396 KB Partially correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Incorrect 1 ms 2392 KB Output isn't correct
6 Incorrect 2 ms 2648 KB Output isn't correct
7 Incorrect 1 ms 2396 KB Output isn't correct
8 Incorrect 2 ms 2396 KB Output isn't correct
9 Incorrect 3 ms 2652 KB Output isn't correct
10 Incorrect 2 ms 2652 KB Output isn't correct
11 Incorrect 3 ms 2652 KB Output isn't correct
12 Incorrect 3 ms 2396 KB Output isn't correct
13 Incorrect 4 ms 2652 KB Output isn't correct
14 Incorrect 5 ms 2692 KB Output isn't correct
15 Incorrect 6 ms 2652 KB Output isn't correct

Subtask #2
0.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Incorrect 8 ms 2652 KB Output isn't correct
5 Incorrect 17 ms 4440 KB Output isn't correct
6 Incorrect 115 ms 10868 KB Output isn't correct
7 Incorrect 123 ms 12880 KB Output isn't correct

Subtask #3
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 4556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 6772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 162 ms 12752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 179 ms 14980 KB Output isn't correct
2 Halted 0 ms 0 KB -