Page 8 Этот код работает везде, кроме как на этом сайте 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 Page 7 Сама задача конечно же довольно простая. Решив ее несколькими способами я каждый раз упирался в превышение объема допустимой памяти на 11 тесте. Соответственно львиная доля времени ушла на осознание того, что же именно потребляет память и на устранение этого узкого места. Как можно было догадаться, память жрали Строки. Я убрал использование string отовсюду кроме считывания данных из консоли. Хранение данных реализовано через два массива int. Для разбора ввода и для вывода ответов в консоль использовались массивы int и char. Вообще, это одна из тех задач, которые отлично иллюстрируют проблему, описанную в FAQ "Как писать решения на C#": "В некоторых задачах потребуется собственная быстрая реализация разбора входных данных и форматирования выходных". Только здесь проблема не в скорости, а в памяти. 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 :) 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. есть ли способы на питоне обойти прожорливость памяти? 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? limit the number of conversions str->int 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; } почему именно stable_sort? c++ простой sort нельзя? c++ Because bubble sort (described in "Notes" chapter) is stable можно, почему нет? Заходит на AC Thanks, with stable_sort everything works. 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 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 I have implemented a stable sort in Rust. I have checked it on task sample array as well as on other sample data that I was generating. I have implemented simple count sort because of small M. But for some reason it doesn't pass test #3. Any ideas what could be wrong? ``` use std::io::{self, BufRead}; fn main() { let stdin = io::stdin(); let mut lines = stdin.lock().lines(); let n: usize = lines.next().unwrap().unwrap().parse().unwrap(); let mut tuples = Vec::with_capacity(n); for _ in 0..n { let line = lines.next().unwrap().unwrap(); let mut line = line.split_whitespace(); let id: u32 = line.next().unwrap().parse().unwrap(); let m: u8 = line.next().unwrap().parse().unwrap(); tuples.push((id, m)) } let tuples = count_sort(&tuples[..]); for (id, m) in tuples { println!("{} {}", id, m); } } fn count_sort(input: &[(u32, u8)]) -> Vec<(u32, u8)> { let mut freq = [0 as u8; 101]; for &(_, m) in input { freq[m as usize] += 1; } let mut output = unsafe { get_empty_vector(input.len()) }; for i in (1..freq.len()).rev() { freq[i - 1] += freq[i]; } for &(id, m) in input.iter().rev() { let new_freq = freq[m as usize] - 1; freq[m as usize] = new_freq; output[new_freq as usize] = (id, m); } output } unsafe fn get_empty_vector<T>(size: usize) -> Vec<T> { let mut vec = Vec::with_capacity(size); let ptr = vec.as_mut_ptr(); std::mem::forget(vec); let result = Vec::from_raw_parts(ptr, size, size); result } ``` I tried implementing mergesort which probably had recursion depth runtime error; bisect insertion to save some memory, but too slow for python list (perhaps a good alternative if I have access to pointer?); heapq is much faster but instable. What are other options? Pages: 8 7 6 5 4 3 2 1 Previous |
|