TLE in KOILINE

[thaitranbt]

include

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool myfunction ( int i, int j){return ( i < j);}
int main () {
    long n ,i,li ;
    long sc, max, order;
    vector<long> a(100001),ans(100001);
    vector<long> b,luu;
         scanf("%ld",&n);
         for ( i = 1; i <= n; i++ ){
               scanf("%ld",&sc);
              a.push_back(sc);
              luu.push_back(i-1);
         }
         for ( i = 1; i <= n; i++){
              scanf("%ld",&order);
              b.push_back(order);
         }
        sort(a.begin(),a.end(),myfunction);
        sc = n-1 ;
        while ( sc >= 0){
           max = -1 ;
           for ( i = 0; i < b.size(); i++) {
              if ( b.at(i) == luu[i] && b.at(i)> max ) {
                  max = b.at(i);
                  li = i;
              }
          }
          sc --;
          a.pop_back();
          ans.at(li) = *(a.end());
         b.at(li) = -1;
         for ( int j = li + 1; j<=n; j++) luu[j] = luu[j] - 1;
       }
         for ( i = 0; i < n ; i++ ) {
              printf("%ld\n",ans.at(i));
        }
return 0;
}

I just start with vector, not mature in it!

[thaitranbt]

I just start with vector!

[leppyr64]

Please use the code tags, it preserves your indentation.

your code

What is the issue with your code? TLE? WA? NZEC?

[thaitranbt]

TLE in test 20th

[thaitranbt]

    #include<stdio.h>
    #include<algorithm>
  int main () {
    long n ,i,li ;
    long sc, max, order;
  long a[100001],ans[100001], b[100001],luu[100001];
    scanf("%ld",&n);
    for ( i = 0; i < n; i++ ){
            scanf("%ld",&a[i]);
          luu[i] = i;
    }
    for ( i = 0; i < n; i++){
          scanf("%ld",&b[i]);
    }
    sort(a,a+n);
    sc = n-1 ;
    //for ( i = 0; i < n; i++ ) cout << a[i] << endl;
    while ( sc >= 0){
    max = -1 ;
    for ( i = 0; i < n;  i++) {
    if ( b[i] == luu[i] && b [i]> max ) {
    max = b[i] ;
    li = i;
    }
    }
    sc --;
   ans[li] = a[sc+1] ;
    b[li] = -1;
    for ( int j = li + 1; j<=n; j++) luu[j] = luu[j] - 1;
    }
    for ( i = 0; i < n ; i++ ) {
    printf("%ld\n",ans[i]);
    }
    return 0;
    }

I simplify that without vector but still TLE!

[leppyr64]

You algorithm is O(n^2). With n being as large as 100000 this complexity is far too slow. That is the reason for the TLE.

[thaitranbt]

I know! But it is the best thing that I could think :mrgreen: