#include <iostream>
using namespace std;

int main()
{
    long N;
    cin >> N;
    long **array = new long*[N];
    for (long i = 0; i < N; i++)
    {
        array[i] = new long[2];
        long temp, temp2;
        cin >> temp >> temp2;
        array[i][0] = temp;
        array[i][1] = temp2;
    }
    cout << endl << endl;

    long l, r, i, k, buf;
    k = l = 0;
    r = N - 2;
    while (l <= r)
    {
        for (i = l; i <= r; i++)
            if (array[i][1] < array[i + 1][1])
            {
                swap(array[i], array[i + 1]);
                k = i;
            }
        r = k - 1;
        for (i = r; i >= l; i--)
            if (array[i][1] < array[i + 1][1])
            {
                swap(array[i], array[i + 1]);
                k = i;
            }
        l = k + 1;
    }
        for (long i = 0; i < N; i++)
        {
            cout << array[i][0] << " " << array[i][1] << endl;
        }
        return 0;
    }

What is wrong with it?( I use bubbleshaker sort.

my program with
while(n < 3)
 printf("there are some stupid tests!\n");
gets Output limit exceeded 3.
Please, check your tests!

I don't understand. I use quicksort and then find solution very fast. MLE #21 say me that
memory limit! I use c#.

Edited by author 26.03.2017 21:16

Edited by author 26.03.2017 21:16

Edited by author 26.03.2017 21:17

Edited by author 26.03.2017 21:37

I think, i do all rigth, but i've WA1=((
I don't understand output type, that's mean what me should to print. Sorry for my English...

var a,b:array[1..15000]of longint; asd,asd1,n,i,j:longint;
begin
read(n);
for i:=1 to n do read(a[i],b[i]);

for i:=1 to n-1 do
  for j:=i+1 to n do
    if b[i]<b[j] then begin
                      asd:=b[i];
                      b[i]:=b[j];
                      b[j]:=asd;
                      asd1:=a[i];
                      a[i]:=a[j];
                      a[j]:=asd1;
                      end;

for i:=1 to n do begin write(a[i],' ',b[i]);writeln;end;
end.

//problem solved (issue of different compilers of my local PC and judge one)

Edited by author 26.03.2017 16:41

//tower.in
1000 60 10
1
2
3
4
5
20170312
666666666
888888888
999999999
427749136024120470
427749136024120471
427749136024120472
-1

//tower.out
427749136024120472
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 4 3
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3 4 5 6 7 6 7 6 7 8 9 8 7 6 5 6 7 8 9 10 9 8 9 10 11
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 2 3 2 3 4 3 4 3 4 5 6 7 8 9 8 9 10 11 12 11 10 9 10 9 10 9 10 9 8 9
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3 2 3 4 5 6 5 4 5 6 5 4 3 4 5 6 7 8 9 10 9 8 9 8 7 6 7 6 5 4 5
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3 4 3 4 5 4 5 6 7 8 9 10 9 8 7 8 9 8 9 10 9 8 9 10 11 12 11 12 13 14 13
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 7 6 5 4 3 2 1 2 3 2 1
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 7 6 5 4 3 2 3 2 1 2 1
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 8 7 6 5 4 3 2 1 2 1 2 1

I finished it in 0.015s.

The solutions were judged in a low performance mode for the last two weeks. Now it's fixed, the solutions are being rejudged.

Remember that you shouldn't check prime numbers (They call an integer satisfying if they both consider or do not consider this integer to be interesting)

GET BIGER HASH NUM !!!!
If your hash number isn't big enough, you will end up with an endless loop.

hell why WA1?
i wanna get my TLE

package main

import (
    "bufio"
    "os"
    "strings"
    "strconv"
)

func main() {

    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)

    buffer, _ := in.ReadString('\n')
    str := []rune(strings.Trim(buffer, "\n"))

    buffer, _ = in.ReadString('\n')
    count, _ := strconv.ParseUint(strings.Trim(buffer, "\n"), 10, 0)
    for k := uint64(0); k < count; k++ {

        buffer, _ = in.ReadString('\n')
        flds := strings.Fields(buffer)

        if []rune(flds[0])[0] == 'c' {
            i, _ := strconv.Atoi(flds[1])
            str[i-1] = []rune(flds[2])[0]
        } else {
            i, _ := strconv.ParseUint(flds[1], 10, 0)
            j, _ := strconv.ParseUint(flds[2], 10, 0)
            if isPali(i-1, j-1, str) {
                out.WriteString("Yes\n")
            } else {
                out.WriteString("No\n")
            }
        }
    }
    out.Flush()
}

func isPali(i, j uint64, str []rune) bool {
    for i < j {

        if str[i] != str[j] {
            return false
        }

        i++
        j--
    }
    return true
}

Edited by author 22.03.2017 08:19

Edited by author 22.03.2017 08:19

Hallo,
On February 1st, 2017 I submitted a solution on Python, which was accepted with the time 0.9 sec.  Yesterday I optimised it and submitted, but got "time limit exceeded" message.  I then tried my original solution (from 01/02/2017), and it also exceeded time limit.

Questions:
1) has something changed in the methodology, or you added some new or modified old tests so it takes more time?

2) is timing dependent on the server load or each solution is tested independently on a dedicated thread? (THis may be a good question for the FAQ)

Thank you in advance.

I'm laughing now ....
I've spent about 3 hours for this problem.
First off, I used Z-function and I tried to treat problem as a string problem. I generated new string and tried to find it. If there is no, that's the answer.
It became not so slow as can seems to be. But TLE#6 got me!
Then I tried to store positions for each digit(0-9) and than tried to search target number using binary search for every digit. It works, but not good enough to pass test#6.
Then I decided to use the straight approach using bool exists[1000000] that indicates whether n is substring. It approach can be done since total length is 10^5, so 10^6 is free for sure.

Since we know several approaches sometimes we use more complex first :)

Can you give me some tests, please? I don't understand why WA.

Тут кто нибудь вообще прощёл тест №11 на Java пользуясь именно Bubble Sort? Что то мне подсказывает что это вообще невозможно с такими ограничениями времени. Но в таком случае, почему в задаче упоминается именно пузырьковый поиск? Или всё таки это возможно, а я где то дико туплю?

import java.io.*;
public class Timus {
        public static void main (String[] args) throws IOException
        {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter out = new PrintWriter (new OutputStreamWriter(System.out));

            int N = Integer.parseInt(in.readLine()), bufer;
            int ID[] = new int[N];
            byte M[] = new byte[N];

            for (int i = 0; i<N; i++)
            {
                String[] s = in.readLine().split(" ");
                ID[i] = Integer.parseInt(s[0]);
                M[i] = Byte.parseByte(s[1]);
            }

            for (int i = 0; i < N-1; i++)
                for (int j = N-1; j > i; j--)
                    if (M[j]>M[j-1])
                    {
                        bufer = M[j];
                        M[j] = M[j-1];
                        M[j-1] = (byte) bufer;
                        bufer = ID[j];
                        ID[j] = ID[j-1];
                        ID[j-1] = bufer;
                    }

            for (int i = 0; i < N; i++)
                out.print("\n" + ID[i] + " " + M[i]);

            out.flush();
        }
}

2
Codeforces Gamma Round 512
29.02.16
5 0
URKOP
17.10.15
12 1
A Accepted

So, i accidentally wrote a suboptimal solution for this problem (stored entire sequences of settings instead of just singular changes from the previous ones), saw it taking 15s (about 8 without the output) to complete max test on my laptop but submitted for fun anyway. Got AC in 0.4s. Go figure.

 sigma (((a*x+b)/c)^k)    l<=x<=r     1<=a,b,c<=10^9    1<=k<=50

how to solve??

http://www.lydsy.com/JudgeOnline/problem.php?id=3913

#include<iostream>
#include<math.h>
#include<algorithm>
#include<string.h>

using namespace std;
int a,b,c,d;
int main()
{
    cin >> a >> b >> c >> d;
    int h = c;
    if(a >= c)
    {
        cout << a;
        return 0;
    }
    while(1)
    {
        if(a == c)
        {
            cout << a;
            return 0;
        }
        a+=b;
        if(c-d >= a) c-=d; else
        {
            if(a > h) cout << h; else
            cout << a;
            return 0;
        }
    }
    return 0;
}