Submission #1157267

Source Code Expand

#include <cstdio>  
#include <cmath>  
#include <ctime>  
#include <string>  
#include <cstring>  
#include <cstdlib>  
#include <iostream>  
#include <algorithm>  
#include <set> 
#include <queue>  
#include <vector>  
#include <map>
#include <complex>
#include <list>
#define pb push_back 
#define lb lower_bound 
#define lowbit(x) (x)&(-x)   
#define forup(i,a,b) for(int i=(a);i<=(b);i++)  
#define fordown(i,a,b) for(int i=(a);i>=(b);i--)  
#define maxn 4000005 
#define INF 1070000000  
#define pa   pair<double,int>
#define  mp  make_pair
#define pi  acos(-1);
#define int ll
using namespace std;  
typedef long long ll;  
typedef unsigned long long ull;  
  
template<class T> inline  void read(T& num){   num = 0; bool f = true;char ch = getchar();   while(ch < '0' || ch > '9') { if(ch == '-') f = false;ch = getchar();}   while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();}   num = f ? num: -num;  } 
int out[100]; 
template<class T> inline 
void write(T x,char ch){  if (x==0) {putchar('0'); putchar(ch); return;}  if (x<0) {putchar('-'); x=-x;} int num=0; while (x){ out[num++]=(x%10); x=x/10;} fordown(i,num-1,0) putchar(out[i]+'0'); putchar(ch); } 
/*========================================================*/
int n,c,k;
int t[maxn];
struct per
{  int siz,col;}p[maxn];
bool cmp(per x,per y)
{return   x.siz<y.siz;}
bool  vis[maxn];
bool check(int x)
{  int sz=p[x].siz;
    forup(i,1,n)
       { if(i==x)  continue;
          if(p[i].siz<=sz*2)
             {  sz+=p[i].siz;}
          else {return 0;} 
       } 
   return 1;
}
signed main()
{  cin>>n; 
forup(i,1,n)
    {  read(p[i].siz);
       p[i].col=i; 
    }
   sort(p+1,p+1+n,cmp); 
    //forup(i,1,n)
    //sum[i]=sum[i-1]+p[i].siz;
  int l=1,r=n;
  while(l<r)
  { int mid=(l+r)>>1;
      if(check(mid))   r=mid;
       else  l=mid;
  } 
  int sta;
  if(check(l)) sta=l;
  else sta=r;
  cout<<sta<<endl;
   forup(i,sta,n)
    {  vis[p[i].col]=1; }
   int cnt=0;
  forup(i,1,n)
    if(vis[i]) cnt++;
    cout<<cnt;
 return 0;
}

Submission Info