Why does

bool comp(pair<int,int>& a, pair<int,int>& b)
{
    return a.second > b.second;
}

not AC with common sort?

Этот код работает везде, кроме как на этом сайте
Runtime error test 1. Почему???

import sys
array4 = dict()
result = ""
for i in sys.stdin.read().split("\n")[1:]:
    array4[str(i.split(" ")[0])] = str(i.split(" ")[1])
def QSort(arr3):
    if len(arr3) < 2:
        return arr3
    else:
        privot, do3, sered, posle = int(arr3[list(arr3.keys())[0]]), dict(), dict(), dict()
        for x, i in arr3.items():
            if int(i) > privot:
                do3[x] = i
            elif int(i) < privot:
                posle[x] = i
            else:
                sered[x] = i
    return {**QSort(do3), **sered, **QSort(posle)}
for t, y in QSort(array4).items():
    result += f"{t} {y}\n"
print(result.strip('\n'))

//URAL-1100-FINAL STANDINGS

//---------------------------------
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'


bool comp(pair<int,int>a,pair<int,int>b)
{
    return a.second>b.second;
}
void sortt(map<int,int>mp)
{
    vector<pair<int,int>>v;
    for(auto it:mp)
    {
        v.push_back(it);
    }

    stable_sort(v.begin(),v.end(),comp);
    for(auto it:v)
    {
        cout<<it.first<<" "<<it.second<<endl;

    }
}
int main()
{
    map<int,int>mp;
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int x,y;
        cin>>x>>y;
        mp[x]=y;
    }
    sortt(mp);


    return 0;
}

Сама задача конечно же довольно простая. Решив ее несколькими способами я каждый раз упирался в превышение объема допустимой памяти на 11 тесте. Соответственно львиная доля времени ушла на осознание того, что же именно потребляет память и на устранение этого узкого места.
Как можно было догадаться, память жрали Строки. Я убрал использование string отовсюду кроме считывания данных из консоли. Хранение данных реализовано через два массива int. Для разбора ввода и для вывода ответов в консоль использовались массивы int и char.

Вообще, это одна из тех задач, которые отлично иллюстрируют проблему, описанную в FAQ "Как писать решения на C#":
"В некоторых задачах потребуется собственная быстрая реализация разбора входных данных и форматирования выходных". Только здесь проблема не в скорости, а в памяти.

почему именно stable_sort?  c++
простой sort нельзя?  c++

limit the number of conversions str->int

Hope it will help someone <3

You need to create a dictionary (dict) with keys from '100' to '0' (keys in str format) and values ​​in the form of empty lists (list) - {'100': [], '99': [], ..., '0 ': []}.

After that, you need to read the commands IDs and their results in a loop, and then add the commands IDs to the dictionary with the key as the commands results - if you get the values ​​"11 2", then add the command ID 11 to the dictionary under the key 2 (command result) - [..., '2': [11], ...].

When we finish adding commands, we will have a sorted dictionary and all that remains is to print the values. In the loop we go through the dictionary and if the value (list) is not empty, then we display all the values ​​in the format "command_id dictionary_key".


Нужно создать словарь с ключами от '100' до '0' (ключи в формате str) и значениями в виде пустых списков (list) - {'100': [], '99': [], ..., '0': []}.

После этого нужно в цикле считывать ID команд и их результат, после чего добавлять ID команд в словарь с ключом в виде результата команды - если получили значения "11 2", значит добавляем ID команды 11 в словарь под ключом 2 (результат команды) - [..., '2': [11], ...].

Когда закончим добавление команд то у нас будет уже отсортированный словарь и останется только вывести значения. В цикле проходим по словарю и если значение (список) не пустой, то выводим все значения в формате "ID_команды ключ_словаря".

#include <iostream>
using namespace std;
int main()
{
    int n,a[100],b[100],c,d,i,j;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i]>>b[i];
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
            if(b[i]<b[j])
            {
                c=b[i];
                b[i]=b[j];
                b[j]=c;
                d=a[i];
                a[i]=a[j];
                a[j]=d;
            }
    for(i=0;i<n;i++)
        cout<<a[i]<<' '<<b[i]<<'\n';
    return 0;
}


Help me! I'm die.
Sorrry,my English is poor.
I will try my best to understand you.

есть ли способы на питоне обойти прожорливость памяти?

Several highly optimized solutions were TLE in Python3.6, though on local run in Linux it shows half of a time on your server. Is there some mistake?

Hi, why is a problem author talking about bubble sort? And why a lot using stl stable_sort? Where is a differents of stl sort?

Question requirements are ordered without changing order

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

const int maxn = 150005;
struct Node
{
    int index;
    int ID;
    int mount;
}node[maxn];

int N;

bool cmp(Node &a, Node &b)
{
    if (a.mount != b.mount)
    {
        return a.mount > b.mount;
    }
    else
    {
        return a.index < b.index;
    }
}

int main()
{
    scanf("%d", &N);
    for (int i=0; i<N; i++)
    {
        scanf("%d%d", &node[i].ID, &node[i].mount);
        node[i].index = i;
    }

    sort(node, node + N, cmp);

    for (int i=0; i<N; i++)
    {
        printf("%d %d\n", node[i].ID, node[i].mount);
    }
    return 0;
}

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

class team{
    public:
        string id;
        int n;
};

bool comp(const team &t1,const team &t2);

int main(){
    int k;
    cin>>k;
    vector<team> T;
    while(k--){
        string temp;
        int num;
        cin>>temp>>num;
        team t;
        t.id=temp;
        t.n=num;
        T.push_back(t);
    }
    stable_sort(T.begin(),T.end(),comp);
    for(int i=0;i<T.size();++i){
        cout<<T[i].id<<" "<<T[i].n<<endl;
    }

return 0;
}

bool comp(const team &t1,const team &t2){
    return t1.n>t2.n;
}

a=[]
for i in range(int(input())):
    c=str(input())
    if len(a)==0 :
        a.append(c)
        continue
    d=(a[0].split())[1]
    d=int(d)
    k=int((c.split())[1])

    if k>=d :
        a.reverse()
        a.append(c)
        a.reverse()
    else:
        for j in range (len(a)):
            h=int((a[j].split())[1])



            if k >= h:
                p = a[:j]
                o = a[j:]
                p.append(c)
                p.extend(o)








for i in range(len(a)):
   print(a[i])


Edited by author 26.09.2018 20:38

I really don't know why I cant reach optimal time. It's always more than 1 sec. Here's my code:

n = int(input())
data = [[] for k in range(101)]
for i in range(n):
    ID, tasks = map(int, input().split())
    data[tasks] += [ID]
for i in range(100, -1, -1):
    for j in data[i]:
        print(j, i)

Meanwhile, I tried to reach time less that 1 sec by not using sorting but as I can see it's not working =(

Edited by author 20.08.2018 16:29

/*
* @Author: eleven
* @Date:   2017-05-21 02:50:38
* @Last Modified by:   eleven
* @Last Modified time: 2018-02-09 14:49:14
*/

// Status : AC ( works with stable_sort )
// doesn't works with sort

#include <bits/stdc++.h>

using namespace std;

#define SIZE 150005

struct team{
    int id;
    int solved;
}teams[SIZE];

bool foo(team lhs, team rhs){
return lhs.solved > rhs.solved;
}

void print(int n ){

    for(int i= 0; i<n ; ++i){
        cout<<teams[i].id<<" "<<teams[i].solved<<'\n';
    }
}


int main(){


    //freopen("in","r",stdin);
    //freopen("out","w",stdout);

    int n ;

    cin>>n;

    for(int i = 0; i<n ; ++i){
        cin>>teams[i].id>>teams[i].solved;
    }

    stable_sort(teams,teams+n ,foo);

    print(n);

    return 0;

}

using namespace std;
#include<iostream>
#include<stdio.h>
#include<algorithm>
long cnt=0;
long heapsize;
long heapsize1;
void heapsort(struct st a[]);
void buildmaxheap(struct st a[]);
void maxheapify(struct st a[],long index);
long left(long a);
long right(long a);
struct st
{
    long serial;
    long f;
    long l;
};


int main()
{
    long n;
    scanf("%ld",&n);
    long s1;
    long s2;

    struct st* a=new struct st[n+1];
    heapsize=n;
    for(long i=1;i<n+1;i++)
    {
     cnt++;
     a[i].serial=cnt;
     scanf("%ld",&s1);
     getchar();
     scanf("%ld",&s2);
     a[i].f=s1;
     a[i].l=s2;
    }
    heapsort(a);
    for(long i=n;i>0;i--)
    {
        cout<<a[i].f<<" "<<a[i].l<<endl;
    }
}
void heapsort(struct st a[])
{
    buildmaxheap(a);
    for(long i=heapsize;i>=2;i--)
    {
        swap(a[i],a[1]);
        heapsize1--;
        maxheapify(a,1);
    }


}
void buildmaxheap(struct st a[])
{
    heapsize1=heapsize;
   for(long i=heapsize/2;i>=1;i--)
   {
       maxheapify(a,i);
   }
}
void maxheapify(struct st a[],long index)
{
    long l1=left(index);
    long r1=right(index);
    long largest;
    if(l1<=heapsize1&&a[l1].l>=a[index].l)
    {
        if(a[l1].l==a[index].l)
        {
            if(a[l1].serial<a[index].serial)
                largest=l1;
        }
         else
                largest=l1;

    }

    else
        largest=index;
    if(r1<=heapsize1&&a[r1].l>=a[largest].l)
    {
        if(a[r1].l==a[largest].l)
        {
            if(a[r1].serial<a[largest].serial)
                largest=r1;
        }
         else
                largest=r1;

    }
    if(largest!=index)
    {
        swap(a[largest],a[index]);
        maxheapify(a,largest); //maintaining property
    }
}
long left(long a)
{
    return 2*a;
}
long right(long a)
{
    return 2*a+1;
}

what is the second test? i have WA on it.

Edited by author 19.05.2018 05:46

Edited by author 19.05.2018 05:46