1490E - Accidental Victory - CodeForces Solution


binary search data structures greedy *1400

Please click on ads to support us..

Python Code:

def main():
    alpha = 'abcdefghijklmnopqrstuvwxyz'
    ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    inf = 1e17
        mod = 10 ** 9 + 7

                                                                                    




    def factorial(n):
        f = 1

        for i in range(1, n + 1):
            f = (f * i) % mod          
        return f

    def factorial_by(n, by):
        f = 1

        for i in range(1, n + 1):
            if i == by:
                continue
            f = (f * i) % mod          
        return f

    def ncr(n, r):
                        num = den = 1
        for i in range(r):
            num = (num * (n - i)) % mod
            den = (den * (i + 1)) % mod
        return (num * pow(den,
                          mod - 2, mod)) % mod

    def primeFactors(num):

        pf = []
        while num % 2 == 0:
            pf.append(2)
            num = num // 2

                        for i in range(3, int(math.sqrt(num)) + 1, 2):

                        while num % i == 0:
                pf.append(i)
                num = num // i

                        if num > 2:
            pf.append(num)

        return pf

    class Node(object):
        def __init__(self, anc, s):
            self.anc = anc
            self.s = s

        def __repr__(self):
            return str(self.s)
            pass

    class DSU:
        def __init__(self, n):
            self.parent = list(range(n))
            self.size = [1] * n
            self.num_sets = n

        def find(self, a):
            acopy = a
            while a != self.parent[a]:
                a = self.parent[a]
            while acopy != a:
                self.parent[acopy], acopy = a, self.parent[acopy]
            return a

        def union(self, a, b):
            a, b = self.find(a), self.find(b)
            if a != b:
                if self.size[a] < self.size[b]:
                    a, b = b, a

                self.num_sets -= 1
                self.parent[b] = a
                self.size[a] += self.size[b]


    def floor(a,b):
        val = a//b
        while val*b > a:
            val -= 1
        return val

    def isprime(num):
        for _ in range(2, int(math.sqrt(num)) + 1):
            if num % _ == 0:
                return False
        return True




    def solve(n,a):

        arr_ind = []
        for i in range(n):
            arr_ind.append((a[i],i+1))
        arr_ind.sort()

        pre = [0]

        for i in range(n):
            pre.append(pre[-1]+arr_ind[i][0])

                winners = [arr_ind[n-1][1]]
        for i in range(n-1,0,-1):
            if pre[i] >= arr_ind[i][0]:
                winners.append(arr_ind[i-1][1])
            else:
                break
            
        return str(len(winners))+"\n" +" ".join(list(map(str,sorted(winners))))



































    
    t = int(input())
    ans = []
    for _ in range(t):
        
        n = int(input())

                
        
        a = [int(x) for x in input().split()]
        
                                        
                                                                        

        ans.append(solve(n,a))

    p = 1
    for answer in ans:
        #        print(answer)
        p += 1


if __name__ == "__main__":
    import sys, threading
    import bisect
    import math
    import itertools
    from sys import stdout
    from collections import defaultdict,deque
    from heapq import heappush, heappop


        import heapq
    from queue import PriorityQueue


            
    input = sys.stdin.readline
    thread = threading.Thread(target=main)
    thread.start()
    thread.join()

C++ Code:

#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define ull unsigned long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
#define deb(x) cerr<<"("<<#x<<"="<<x<<","<<__LINE__<<")"<<endl; 
template <typename T>
void debvec(vector<T>v){    
    for(auto i:v)cerr<<i<<" ";cerr<<"\n";
}
template <typename T>
void debarr(int n, T arr[]){
    for(int i=0;i<n;i++)cerr<<arr[i]<<" ";
    cerr<<"\n";
}
ll ll_range = 9223372036854775807; //9*1e18 + 223372036854775807;
int int_range = 2147483647; // 2*1e9 + 147483647;
// cout << fixed << setprecision(11) <<endl;

const int mod=998244353;

ll find_fact(ll n){
  function<ll(ll)> ff = [&](ll n){
    if(n==1)return 1LL;
    return n*ff(n-1);
  };
  return ff(n);
}

vector<ll> sieveOfErastothenes(ll n){
  vector<bool> is_prime(n+1, true);
  vector<ll> res;
  // res.push_back(1);
  is_prime[0] = is_prime[1] = false;
  for(ll i = 2; i*i<= n; i++){
    if(is_prime[i]){
      for(ll j=i*i; j<=n; j+=i){
        is_prime[j]=false;
      }
    }
  }
  for(ll i=0;i<=n;i++){
    if(is_prime[i]){
      res.push_back(i);
    }
  }
  return res;
}

ll bin_search(ll l, ll r, vector<ll>v){
  l--;
  r++;
  while(r-l>1){
    int mid=l+(r-l)/2;
    if(v[mid]==0){
      l=mid;
    }else{
      r=mid;
    }
  }
  return r; // r is first predicate change value
}

ll squareRoot(ll n){
  ll l=1, r=3000000001;
  while(r-l>1){
    ll mid = l + (r-l)/2;
    if((mid*mid)<=n){
      l=mid;
    }else{
      r=mid;
    }
  }
  if(l*l==n){
    return l;
  }else{
    return -1;
  }
}

ll cubeRoot(ll n){
  ll l = 1, r = 2080084;
  while(r-l>1){
    ll mid = l + (r-l)/2;
    if(mid*mid*mid<=n){
      l=mid;
    }else{
      r=mid;
    }
  }
  return r-1;
}

int dp[102];

bool check(vector<int>v, int x){
  ll sum=0;
  int n=v.size();
  for(int i=x;i>=0;i--)sum+=v[i];
  for(int i=x+1;i<v.size();i++){
    if(sum<v[i]*1LL)return false;
    sum+=v[i]*1LL;
  }
  return true;
}

void solve(){
  int n;
  cin>>n;
  vector<int>v(n);
  vector<int>s(n);
  for(int i=0;i<n;i++){
    cin>>v[i];
    s[i]=v[i];
  }
  sort(all(v));

  int l=-1,r=n;
  while(r-l>1){
    int mid=l+(r-l)/2;
    if(check(v,mid)){
      r=mid;
    }else{
      l=mid;
    }
  }
  int ans=v[r];
  cout<<n-r<<endl;
  vector<int>anss;
  for(int i=0;i<n;i++){
    if(s[i]>=ans)anss.push_back(i+1);
  }
  for(auto&i:anss){
    cout<<i<<" ";
  }cout<<"\n";
}

int32_t main()
{
    fast;
    ll t=1;
    cin>>t;
    for(int i=0;i<t;i++){
      solve();
    }
    return 0;
}


Comments

Submit
0 Comments
More Questions

1542A - Odd Set
1567B - MEXor Mixup
669A - Little Artem and Presents
691B - s-palindrome
851A - Arpa and a research in Mexican wave
811A - Vladik and Courtesy
1006B - Polycarp's Practice
1422A - Fence
21D - Traveling Graph
1559B - Mocha and Red and Blue
1579C - Ticks
268B - Buttons
898A - Rounding
1372B - Omkar and Last Class of Math
1025D - Recovering BST
439A - Devu the Singer and Churu the Joker
1323A - Even Subset Sum Problem
1095A - Repeating Cipher
630F - Selection of Personnel
630K - Indivisibility
20B - Equation
600B - Queries about less or equal elements
1015A - Points in Segments
1593B - Make it Divisible by 25
680C - Bear and Prime 100
1300A - Non-zero
1475E - Advertising Agency
1345B - Card Constructions
1077B - Disturbed People
653A - Bear and Three Balls