Wonder why this task has a 147 complexity. Just sort and write

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

const int maxn = (int) 1e5;
int a[maxn];

int main() {
    int n, x;
    cin >> n;
    fo(i, n) {
        cin >> a[i];
    }
    sort(a, a + n);
    string str;
    cin >> str >> n;
    fo(i, n) {
        cin >> x;
        cout << a[x - 1] << '\n';
    }
    re 0;
}

Just sort() numbers...
It will take approximately 1e5 * log(1e5) ≈ 1e6 operations, which is not that long to compute.

Edited by author 02.12.2017 00:54

program z1026;
var n,k,i,j,nomer:integer;
    count:array[1..5000]of integer;
    a,rez:array[1..100000]of integer;
    z:array[1..100]of integer;
    s:string;
begin
     read(n);
     for i:=1 to n do read(a[i]);
     read(s);
     read(k);

     for i:=1 to 5000 do count[i]:=0;
     for i:=1 to n do inc(count[a[i]]);
     nomer:=1;
     for i:=1 to 5000 do
         for j:=1 to count[i] do begin
             rez[nomer]:=i;
             inc(nomer);
         end;

     for i:=1 to k do read(z[i]);
     for i:=1 to k do writeln(rez[z[i]]);
end.

Answer for test1 is
  121
  121
  7
  123

This problem can be solved without realisation of sorting. :)

алгоритм сделал и работает, но не проходит проверку, говрит что напечатал слишком много букафф,,, мне кажется я неправильно читаю К, не знаю как перепрыгнуть через те решетки :(

int K;
char ch;
scanf("%s%d",&ch,&K);

Just use the countsort:)

Edited by author 15.12.2012 09:15

Edited by author 15.12.2011 23:01

if you got WA on this test try to change SHORT on INT or CHAR.
it looks like an error in task.

maybe it is not the best solution, but

using System;
using System.Collections.Generic;

namespace _1026
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            List<int> z = new List<int>();
            for(int i = 0; i < n; i++)
                z.Add(int.Parse(Console.ReadLine()));
            z.Sort();
            Console.ReadLine();
            int k = int.Parse(Console.ReadLine());
            for (int i = 0; i < k; i++)
                Console.WriteLine(z[int.Parse(Console.ReadLine())-1]);

        }
    }
}

When i use bubble alg i have TLE #5(it's normal, i understand that), but when i use quick sort, i have WA#3, why??? What is wrong?

var b,a:array[0..100010]of longint;
 x,i,n:longint;
begin
 readln(n);
 for i:=1 to n do begin readln(x); inc(a[x]); end;
 x:=0;
 for i:=0 to 5000 do while(a[i]>0)do begin inc(x); dec(a[i]); b[x]:=i; end;
 readln; readln(n);
 for i:=1 to n do begin read(x); writeln(b[x]); end;
end.

Edited by author 20.01.2010 18:28

Could anyone help me?
This code get CRASH...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
// Input Database
int num_elem_db;
cin >> num_elem_db;
vector<int> data_vector (num_elem_db, 0); // Vector for data
for (int i = 0; i < num_elem_db; ++i)
{
   int aux_elem;
   cin >> aux_elem;
   data_vector[i] = aux_elem;
}
cout << "###" << endl;
// SORTING VECTOR OF DATA
sort( data_vector.begin( ), data_vector.end( ) );
// Input queries
int num_queries;
cin >> num_queries;
vector<int> query_vector (num_queries, 0); // Vector for queries
for (int j = 0; j < num_queries; ++j)
{
   int aux_query;
   cin >> aux_query;
   query_vector[j] = aux_query;
}
for (int k = 0; k < num_queries; ++k)
{
   cout << data_vector[query_vector[k]-1] << endl;
}
return 0;
}

var hash:array [1..5001] of longint;
    i,j,k,n,m,ch,zap:longint;
    s:string;
begin
  readln(n);
  for i:=1 to n do
    begin
      readln(ch);
      inc(hash[ch]);
    end;
  readln(s);
  readln(k);
  for i:=1 to k do
    begin
      readln(zap);
      for j:=1 to 5000 do
        begin
          if zap<1 then
                     begin
                       writeln(j-1);
                       break;
                     end
                   else zap:=zap-hash[j];
        end;
    end;
end.

WA Test #2....

if you miss it, you will crash on #5

Edited by author 01.10.2008 01:54

does a program with order O(n*max(K)) can get accepted.
A modified version of bubble sort can do this.Note that
after k passes bubble sort has first k maximum elements.
If u find maximum value of index that is being queried and calling the below function with that maximum value will do the trick for you.Try submitting the problem using this idea.I haven't submitted by this idea
for(i=0;i<=k;i++)
    for(j=i+1;j<n;j++)
          if(a[i]>a[j]) swap(a[i],a[j]);

It works allright, I tested it on many test. Help me please, my code is here.
{$apptype console}
var a: array [1..5000] of longint;
    rez: array [1..150000] of longint;
    i, j, k, n, m, x: longint;
    s: string;
begin
{ reset(input, 'input.txt');
 rewrite(output, 'output.txt');
} readln(n);
 for i:=1 to n do
 begin
  readln(x);
  inc(a[x]);
 end;
 m:=0;
 for i:=1 to 123 do
 begin
  for j:=1 to a[i] do
  begin
   inc(m);
   rez[m]:=i;
  end;
 end;
 readln(s);
 readln(k);
 for i:=1 to k do
 begin
  readln(x);
  writeln(rez[x]);
 end;
{ close(input);
 close(output);
}end.

p.s. excuse me for my bad english =)

I used binary search tree with
simple Aggregation profusion

Edited by author 27.02.2008 22:10

Edited by author 27.02.2008 22:11