Common BoardI used DSU algorithm and AC 0.046. test: 10 4 5 3 6 9 10 8 7 2 1 answer: Not a proof. good test tho I used stack & queue and got AC I used DSU algorithm and AC 0.046. test: 10 4 5 3 6 9 10 8 7 2 1 answer: Not a proof. Thanks for the test case... Helped a lot to find bug in my algo. I am wondering how to use DSU here... Would you please mail me your idea? ealham86@gmail.com Thanks again. The hint was great. Stack + queue can get you AC in 0.031 Admins, please increase Memory Limit in this task. It is wrong that solutions with O(Q*log2(10^9)) memory - segment tree on hash table - has not got any chance to pass Memory Limit without additional input queries coordinates compression (because 100000 * 30 * (3*double + char) is obviously > 64 Mb). This data structure is quite complex even without input queries coordinates compression, why not to AC such solutions? Nowadays commonly used ML is 256 Mb, not 64. Edited by author 19.05.2024 12:37 Edited by author 19.05.2024 12:39 There is only one eligible lowered numbered ball at any round. Keeping track of this should result in O(n) solution Stack 1,10,100,1000,10000,100000,... vertically: 1 10 100 1000 10000 100000 ... the cumulative sums of digits from the top are: 1,3,6,10,15,21,... which are in the form of combination(N,2) = N*(N-1)/2 checking whether one is at Kth digit is the same as finding if there is integer solution to: N*(N-1)/2 = K-1 one way is to solve the quadratic equation for N (in double) and cast N to integer and check the above relation. regards, So Sui Ming Edited by author 16.01.2024 19:27 Edited by author 16.01.2024 19:27 Great solution, So Sui Ming, I did not think about that one in particular. I just use prefix sums and binary search. If you write down the sequence and it's index starting from 1. You will notice that if you do prefix sum ( half interval way , so starting from 0, the first element, first element + second element, etc. ) up till sum <= MAX ( 2^31 - 1 ), you will get 65535 numbers in a sorted way. In this way, notice, that the numbers in this prefix_sum array are all index s.t. digit = 1. You still need to +1 in every position of prefix_sum array, because of 1-index of input. Now you read input number K and do binary search on the prefix sum array. If you did find, great! It is 1. Otherwise, it is 0. Write down the sequence, on paper, by hand. Now, right down the index of each digit on the sequence. Do you know prefix sums and binary search? It's kinda useful for many problems btw... Edited by author 15.05.2024 05:54 I solved 1009 and 1012. Now im using new algorithm (log(n)) and program works fast and correct with my tests. Can you give more tests? I solved 1013, my mistake was multiplication of large numbers, i use long arithmetic for multiplication and uint64 for variables and get Accept My code is here: -------------- #include <iostream> using namespace std; int compare(const void * x1, const void * x2) { return (*(int*)x1 - *(int*)x2); } int main() { long N; cin >> N; int *m = new int [N]; for (int i = 0; i < N; ++i) { cin >> m[i]; } qsort(m, N, sizeof(int), compare);
if (N % 2 == 0) { cout << (((m[(N - 1)/ 2] + m[N / 2]) / 2.0)*10)/10; } else { cout << m[N/2]; } return 0; } -------------- Tell me please where I made a mistake Try the following test: 4 2147483647 2147483647 2147483647 2147483647 how to bypass this test? I tried to use if(arr[n / 2] == -1)cout << "2147483647"; but I still have WA on test 5 I can't understand it... If N1 takes 2 stones at first move, he will lose, won't he? 1:8 - 2 = 6 2:6 - 2 = 4 1:4 - 2 = 2 2:2 - 1 = 1 1:1 - 1 = 0 Please, tell me, where I'm wrong? I understood my mistake. Sorry. if the cube is at e2, neighbors are: e1 (near), e3 (far), d2 (left) and f2 (right) for your convenience 24 orientations of cube: 1 2 3 4 5 6 1 2 4 5 6 3 1 2 5 6 3 4 1 2 6 3 4 5 2 1 3 6 5 4 2 1 4 3 6 5 2 1 5 4 3 6 2 1 6 5 4 3 3 5 1 6 2 4 3 5 2 4 1 6 3 5 4 1 6 2 3 5 6 2 4 1 4 6 1 3 2 5 4 6 2 5 1 3 4 6 3 2 5 1 4 6 5 1 3 2 5 3 1 4 2 6 5 3 2 6 1 4 5 3 4 2 6 1 5 3 6 1 4 2 6 4 1 5 2 3 6 4 2 3 1 5 6 4 3 1 5 2 6 4 5 2 3 1 test: 4 1 4 2 3 6 5 1 4 3 6 5 2 1 4 5 2 3 6 1 4 6 5 2 3 ans: 1 1 2 3 4 Can you send me solution on elsocm5@gmail.com? Thank You! It would be interesting to solve such a problem on an arbitrary graph (not a tree) or to say that there is no solution for such a graph. Please add the following testcase: 869637034218881024 = 2^18 * 1806487 * 1836383 The answer should be "Yes". My solution prints "No" and nevertheless has AC. Thank you! Good test. I found another good one. 999979520100663296. I think it's stronger. However I got AC before, but i was looking for a good test. Edited by author 29.10.2019 00:37 One of the largest allowed numbers 999999999987679232 = 2^19 * 1907348632789 where the second multiplier is a prime number. For WA12 try this: 9126492316491641269352615215701236589213658621356281376589216562319562396592381659862195621281E-190 100 # Output must be: 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009126 What is test #2? Try this: .234 2 .2 2 # Answers: 0.23 0.20 3 times! what the reason? vc++ 0.328 sec g++ 1.078 sec upd. in 3 problems vs is really faster than g++ (2-3 times). Compiler problem? Edited by author 28.10.2014 17:39 Edited by author 28.10.2014 17:39 LOL I have AC in G++11 with time 0.093 s, some other people have AC with 0.031 s. How did you solve this problem with 1.078 s? xD This is absolutely not true |
|