Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
PBDS_TREE SOLUTION | khdz | 1090. Теперь ты в армии | 25 июл 2021 00:44 | 1 |
You can use pbds_tree to solve this problem. PBDS Tree function named "order_by_key" will solve the problem like: find number of elements, which lower than x |
Hint | 👾_challenger128_[PermSU] | 1090. Теперь ты в армии | 8 ноя 2020 18:46 | 1 |
Hint 👾_challenger128_[PermSU] 8 ноя 2020 18:46 You should find the permutation with the maximum number of inversions. You can use segment tree to calculate inversions for each element, just store sorted leafes in each node. |
WA2 | Dimitar Dimitrov | 1090. Теперь ты в армии | 29 апр 2020 23:28 | 3 |
WA2 Dimitar Dimitrov 20 июл 2009 16:16 Could you give me some test data ? Re: WA2 Tudor Zaharia 13 авг 2011 18:47 Re: WA2 blunder woman 29 апр 2020 23:28 Perhaps you accepted k,n instead of n, k as input. |
WA #3 | M@STeR.SoBG | 1090. Теперь ты в армии | 16 апр 2020 22:35 | 7 |
WA #3 M@STeR.SoBG 9 июл 2007 16:28 Could anybody suggest the 3-rd test???? i don't know my mistake. :-( 5 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 the right one is 1 perhaps your programme give 0 A very useful test data! Thanks a lot can't be! i'm fighting with 3rd test for more than hour. And when i test your numbers i get 1 as answer, but still not passing test. |
Who can give me an AC program? | zzq | 1090. Теперь ты в армии | 29 ноя 2019 21:54 | 4 |
Who can give me an AC program? no Edited by author 29.11.2019 21:57 Edited by author 29.11.2019 21:57 |
HINT. To all whose solution using merge sort gets WA on test #5. | Vladislav Nikolaev | 1090. Теперь ты в армии | 4 май 2019 18:57 | 1 |
Solving the problem using the merge sort approach (counting inversions while merging subsequences - plus one inversion in a case of element from the left subseq greater than the element from the right) looks feasible (and maybe evident) to implement. But there is one caveat: it is crucial to count not only the one inversion in a case *cur_left > *cur_right, but count elements in a range [cur_left + 1, right_begin) as "inverted" too. That follows from the fact that merged subarrays are sorted in ascending order, so if we encountered the (*cur_left > *cur_right) case, then elements in a range [cur_left + 1, right_begin) satisfies that too and could be counted as inversions. Hope I stated that clearly. Edited by author 04.05.2019 18:59 Edited by author 06.05.2019 06:44 |
HELP! merge_sort gets WA#5 ,who can give me some test cases,please? | Fighting | 1090. Теперь ты в армии | 12 мар 2016 14:12 | 2 |
|
test data for WA 2 ? | Tom | 1090. Теперь ты в армии | 2 июн 2015 12:10 | 4 |
pls give me some test data, dont know what s wrong with code. greetings. PLEASE NOTE what N and K represent;N represents colums and k represents rows. My code was wrong because of this;Hope you can get help. Thanks!!! I made such mistake :( |
WA in test #7 ?? | naros1988 | 1090. Теперь ты в армии | 24 май 2013 20:55 | 2 |
Can someone give me the test #7. I've got WA in this test. Thank's. Please try for the test: 2 2 1 2 2 1 The correct answer: 2 |
Help me pls.WA #2 | Accepted | 1090. Теперь ты в армии | 5 мар 2013 19:02 | 1 |
Help me!!!I got WA#2 Please give me some tests... I use merge sort. |
fenwick tree rulezzz!!! :-) | Ilya Mitin (1) | 1090. Теперь ты в армии | 3 авг 2011 00:26 | 5 |
oh, YES! This is brilliant data structure =) goood thing ) horrible code: #pragma comment(linker,"/stack:3000000") #include <iostream> int X[10100],n,k,r,h=1e9,g,x,i,j,l; int main(){ if(!j)for(i=n;i;X[i--]=0); if(!l&!j)std::cin>>n>>k; if(l<k){ std::cin>>x; for(i=x;i;r+=X[i],i-=i&-i); for(;x<=n;X[x]++,x+=x&-x); ++j==n?++l,(r<h?h=r,g=l:0),j=r=0:0; main(); } else std::cout<<g; } Edited by author 10.04.2011 19:41 it's the number of swaps in a bull sort. Edited by author 03.08.2011 02:27 |
RB tree | muhammad | 1090. Теперь ты в армии | 14 июл 2010 20:37 | 1 |
AC with RB tree but horrible time(.359 sec) please somebody tell me algorithm to AC in .015 sec. Thanks in advance |
WA #7 | testujecos | 1090. Теперь ты в армии | 16 апр 2010 03:27 | 2 |
WA #7 testujecos 16 апр 2010 01:08 Any1 could give me details about it? No idea wheres my mistake I have no f... idea:/ i have WA #4 or #8. could you tell me why?:( |
WA #6 Help me please......... | FreezingCool | 1090. Теперь ты в армии | 9 мар 2009 19:18 | 1 |
Can anyone tell me what is test number 6??? I used BIT and i get WA at test numebr 6... Help me please |
Who can give me the test #5 | Team CHANT - The TESTER | 1090. Теперь ты в армии | 24 фев 2009 15:56 | 2 |
Try this test 3 3 1 2 3 3 1 2 3 2 1 right answer is 3 Edited by author 05.03.2009 18:23 |
WA for test #5 | Luan Nguyen | 1090. Теперь ты в армии | 24 фев 2009 15:55 | 2 |
Could anyone show me what the input for test #5 is? I can't figure out why my solution fails this test case. Thanks a lot. Try this test 3 3 1 2 3 3 1 2 3 2 1 right answer is 3 Edited by author 05.03.2009 18:22 |
TLE#4 with my code, help!! | Bobur | 1090. Теперь ты в армии | 28 окт 2008 15:08 | 8 |
var i, j, q, key, n, k, k1, max, row : integer; a : array [1..10000] of integer; begin read(n, k); row := 1; max := 0; for k1 := 1 to k do begin for i := 1 to n do read(a[i]); q := 0; For j:=2 to n do Begin Key:=a[j]; I:=j-1; While (i>0) and (A[i]>key) do Begin A[i+1]:=a[i]; inc(q); Dec(i); End; A[i+1]:=key; End; if max < q then begin max := q; row := k1; end; end; writeLn(row); end. here another code but yet TLE#4!! var b : array [1..10000] of smallint; j, n, k, x : smallint; max, s : integer; i, m, q : byte; begin read(n, m); q := 1; max := 0; for i := 1 to m do begin s := 0; for j := 1 to n do begin read(x); b[x] := j; end; for j := 1 to n do begin s := s + b[j] - j; x := b[j]; for k := b[j] downto j + 1 do b[k] := b[k-1]; b[j] := x; end; if max < s then begin max := s; q := i; end; end; writeLn(q); end. You should have nearly O(k*n*logn) (mayby O(k*n*sqrt(n)) algo to avoid TLE . What's about yours? i don't understand you, pls ubderstand and give me some hints var a, b, c : array [1..10000] of smallint; j, n, k : smallint; max, s : integer; i, m, q : byte; begin read(n, m); q := 1; max := 0; for i := 1 to m do begin s := 0; for j := 1 to n do begin read(a[j]); b[a[j]] := j; c[j] := 0; end; for j := 1 to n-1 do begin s := s + b[j] - j+c[j]; for k := a[b[j]] to b[j]-1 do inc(c[k]); end; if max < s then begin max := s; q := i; end; end; writeLn(q); end. Hey, I got TLE on this code with O(k*n*lgn) using Indexed trees. My code is attached for reference: #include<iostream> #include<vector> #include<cstdio> #include<algorithm> using namespace std; int bit[10001]; bool myfunc(vector<int> a,vector<int> b) { if(a[0]>b[0]) return true; return false; } void update(int x,int n) { int i; for(i=x;i<=n;i+=i&-i) bit[i]++; } int getval(int x) { int i,ans=0; for(i=x;i>0;i-=i&-i) ans=ans+bit[i]; return ans; } main() { int n,k,ans=0,ind; scanf("%d %d",&n,&k); int cas=1; while(k--) { int i;
vector<vector<int> > arr; vector<int> emp; arr.clear(); for(i=0;i<n;i++) { arr.push_back(emp); arr[i].push_back(0); scanf("%d",&arr[i][0]); arr[i].push_back(i+1);
} sort(arr.begin(),arr.end(),myfunc); memset(&bit,0,sizeof(bit)); // cout<<bit[1]<<endl; int val=0; for(i=0;i<n;i++) { // cout<<arr[i][1]<<" "; //cout<<val<<" "; val=val+getval(arr[i][1]); update(arr[i][1],n);
} // cout<<endl;
if(ans<val) {ans=val;ind=cas;} cas++; } printf("%d",ind); // cin>>ind; } Any hints? This is not an A+B problem and you should use a more efficient algorithm to avoid using a lot of time. |
what's the approach to get AC in 0.015s? | AlainDelon | 1090. Теперь ты в армии | 2 июл 2008 14:14 | 2 |
I have tried using bucket search( N*sqrt(N)) and segment tree based search( N*log(N)), but still only get AC in 0.1s Anyone can shed some light on this? I have seen someone mentioned mergsort, is this the point? Well, I've also tried merge sort approach(use iterative mergesort instead of recursive), but still only get AC in 0.078s what's the point to boost it into 0.015s? Anyone can shed some light? Thanks a lot! |
some examples for the third test please | Valentin Popa | 1090. Теперь ты в армии | 1 июл 2008 19:00 | 5 |
why insert sort doesn't work? i've found my mistake: never display 0 when the first row is 1 I have tried both bucket sort and segment tree based(nlogn) approaches, but seems both can not beat the time limit? how to get the runtime to 0.015s? |
I know that SBT works! | lonelycorn | 1090. Теперь ты в армии | 12 май 2008 18:21 | 3 |
at first i wrote bst,and i got tle at testcase 3. Now i know that i should have written SBT such as treap. <Chinese>闫X远,“SBT”是陈启峰大牛的“Size Balanced Tree”的专用简称,和Treap不是一码事。你大概是想说“平衡二叉树”吧?这个题用SBT, Treap,或者一种O(nlogn)的基于归并排序的算法都能AC。</Chinese> lonelycorn, the word "SBT" is for Chen Qifeng's "Size Balanced Tree", which is different from Treap. I think you were saying "Balanced BST". And yes, treap and SBT both work, and a simple algo.,O(nlogn) based on mergesort also works. I've written AVL Tree in Java and AC in 0.7 sec. Be careful, this solution should work fast, or will get TLE! |