Why does bool comp(pair<int,int>& a, pair<int,int>& b) { return a.second > b.second; } not AC with common sort? You are not following the bubble sort ordering :) Этот код работает везде, кроме как на этом сайте 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; } You are expecting the map to preserve the order. It does not - it sorts by key. Try using unordered_map<int, int> mp Сама задача конечно же довольно простая. Решив ее несколькими способами я каждый раз упирался в превышение объема допустимой памяти на 11 тесте. Соответственно львиная доля времени ушла на осознание того, что же именно потребляет память и на устранение этого узкого места. Как можно было догадаться, память жрали Строки. Я убрал использование string отовсюду кроме считывания данных из консоли. Хранение данных реализовано через два массива int. Для разбора ввода и для вывода ответов в консоль использовались массивы int и char. Вообще, это одна из тех задач, которые отлично иллюстрируют проблему, описанную в FAQ "Как писать решения на C#": "В некоторых задачах потребуется собственная быстрая реализация разбора входных данных и форматирования выходных". Только здесь проблема не в скорости, а в памяти. почему именно stable_sort? c++ простой sort нельзя? c++ Because bubble sort (described in "Notes" chapter) is stable можно, почему нет? Заходит на AC Thanks, with stable_sort everything works. 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_команды ключ_словаря". There is no bubble sort, but I finally did it as you suggested to fit in memory limit. Thnx) import sys dict ={} for x in range(100,-1,-1): dict.update({str(x):[]}) def process(line): k = [x for x in line.split()] if len(k)!=1: dict[k[1]].append(k[0]) for line in sys.stdin: process(line) for x, y in dict.items(): if y: for t in y: print(t, x) #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. Sort declared in the task is stable. Your sort isn't stable Let we have scores: ("team1", 10), ("team2", 10), ("team3", 15). Your code when i=0, j=2 swaps team1, team3: ("team3", 15). ("team2", 10), ("team1", 10). Note: when you fix your sort you'll face the fact real bubble sort is too slow. Thank you, dear! You are my saver! Thank. Now everything stopped at MLE есть ли способы на питоне обойти прожорливость памяти? 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? It is definitely broken, because same code works in Python 2 It is not broken. I managed to solve it with Python 3.6 There is one more way to solve it in Python 3 without sorting 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; } I don't know why, but i have tha same problem. WA with sort, AC with stable_sort *go to read faq's* #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <algorithm> using namespace std; pair <int, int> a[150000]; int n; bool comp(pair <int, int> a, pair <int, int> b) { return a.first > b.first; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &a[i].second, &a[i].first); stable_sort(a, a + n, comp); //sort(a, a+n,comp); for (int i=0;i<n;i++) printf("%d %d\n", a[i].second, a[i].first); return 0; } OK, i've found yhe answere - stable_sort keeps the relative order berween equal elements... because this is stable sort)) 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 |
|