#include <iostream>

using namespace std;

int prime[15001];
bool num[163848];
void sieve() {
    num[2]=true;
    prime[1]=2;
    long int i,j,k;
    for(i=3;i<163848;i+=2) num[i]=1;
    for(i=2,j=3;i<=15000;j+=2) {
        if(num[j]) {
            for(k=j;k*j<=163848;k+=2) num[k*j]=0;
            prime[i]=j;
            i++;
        }
    }
}

int main() {
    sieve();
    int t;
    cin>>t;
    while(t--) {
        int m;
        cin>>m;
        cout<<prime[m]<<endl;
    }
}


Why am I getting RTE in test #1?

Edited by author 13.09.2019 08:33

does anybody know anything about WA on that test?

I got AC in 0.125s and 284KB!!!
If you want my AC code,post me:happyzeyu@163.com

Edited by author 25.12.2006 17:30

Edited by author 25.12.2006 17:30

If you have problems with test case 6, then please check the following:


If you have wrong anwer at test 6, try this test:
4 3
3 4 5

Correct answer: 1
Because at ith minute, there is only a[i] cars come to the traffic jam. Good luck to you!

Thanks to sign_in158.

n=2984210864
21975
21818
11974
11967
11964
11964
11964
11907
11707

n=120
22
53
23
22
22
22
22
22
22
22

n=1000000000
788888898
900000001
900000000
900000000
900000000
900000000
900000000
900000000
900000000
900000000

n=1595999
887689
1594800
998800
998800
998800
994800
897800
897800
897800
893800

n=2009999
1112889
2204000
1214000
1204000
1204000
1204000
1204000
1204000
1204000
1204000

n=123456789
96021948
130589849
100589849
96589849
96089849
96029849
96022849
96022049
96021959
96021949

n=10000
2893
4001
4000
4000
4000
4000
4000
4000
4000
4000

n=20000
6893
18000
8001
8000
8000
8000
8000
8000
8000
8000

n=30000
10893
22000
22000
12001
12000
12000
12000
12000
12000
12000

n=9999
10893
22000
22000
12001
12000
12000
12000
12000
12000
12000

#include <iostream>
#include <math.h>
#include <iomanip>
#include <vector>
#include <map>
#include <string>
#include <algorithm>


using namespace std;


int main()
{
    int n;
    cin >> n;
    vector<int> vec;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        vec.push_back(num);
    }
    int max = 0;
    int sum = 0, seredina = 0;
    int index = 0;
    multimap<int, int> index_sum;
    for (int i = 2; i < vec.size(); i++) {
        sum = 0;
        if (vec[i] >= vec[i - 1] && vec[i - 1] >= vec[i - 2]) {
            sum += vec[i] + vec[i-1] + vec[i-2];
            index_sum.insert(pair<int, int>(i, sum));
        }
    }
    for (auto it = index_sum.begin(); it != index_sum.end(); it++) {
        if (it->second > max) {
            max = it->second;
            sum = max;
            seredina = it->first;
        }
    }
    cout << sum << " " << seredina;
    return 0;
}

Edited by author 30.10.2019 21:02

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <string>
#include <cstdlib>

using namespace std;

void optimization() {
     cin.tie(nullptr);
     ios_base::sync_with_stdio(false);
}


int main() {
     optimization();

     string s;
     int k = -1;
     cin >> s;
     char c[200000];

     for (char & i : c) {
          i = ' ';
     }

     for (char i : s) {
          if (k > -1) {
               if (c[k] == i) {
                    c[k] = ' ';
                    k--;
               } else {
                    k++;
                    c[k] = i;
                    continue;
               }
          }
          else {
               k++;
               c[k] = i;
          }
     }
     for (char i : c) {
          if (i != ' ') {
               cout << i;
          }
     }

     return 0;
}

You can use Disjoint-set data structure.

Please, help.

Solution is Minimum spanning tree (Kruskal or Prim Algorithm). Put low cost on tunnels, and much higher one on bridges with using priority queue ;)

Used bfs instead dfs

I managed to get rid of WA using these two test cases:

in:
1
dcbbbdbdbbacaaaddbdcbbbdbbdbbadacbbaaddbaddbddacaa
out:
15577

in:
1
abcccacccbcabaaaacbbabbcaaaaacaaaaacaacacbbacbcaba
out:
15236

In test #23 it seems that n is large. So, to pass TLE #23, make sure your code is running fast enough for n = 100 000 and each test contains a single letter.

I used ternary search for this problem
limits
-50000:50000  leads to wa18
-100000:100000 got wa1
-90000:90000 was AC

is there a normal solution without finding such segment?

If you have WA #5 try below test:
2 5
2 3 9 2 100
1 2 5 4 100
2 1
1 5

Correct answer is 0.

Can someone provide a test, that makes the following code get TLE?

// ITNOA
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n;
    cin >> n;
    int cnt = 0;
    for (ll i = 2;i*i <= min((ll)1e18, n);i++)
        while (n%i == 0)
        {
            n /= i;
            cnt++;
        }
    if (n > 1)
        cnt++;
    if (cnt == 20)
        cout << "Yes\n";
    else
        cout << "No\n";
}

Graph can have loops and multiple edges.

Edited by author 28.10.2019 20:10

var
a:integer;
begin
read(a);
if a=0 then write(5);
if a=1 then write(21);
if a=2 then write(12);
if a=3 then write(2);
if a=4 then write(1);
if a=5 then write(4);
if a=6 then write(6);
if a=7 then write(1);
if a=8 then write(4);
if a=9 then write(4);
if a=10 then write(1);
if a=11 then write(0);
if a=12 then write(1);
if a=13 then write(1);
end.

Edited by author 28.10.2019 15:01

Because of p*=(i%m) was WA. When I wrote p=(p*i)%m instead of p*=(i%m) then  I got AC
Why???

What is in 3 test ?

MY CODE IS:

#include<bits/stdc++.h>
using namespace std;

vector < int > heap;

/////MINHEAP

void ADD( int m )
{
  heap.push_back(m);
  int j = heap.size()-1;

  while( j != 1 &&  heap[j] < heap[j/2] )
  {
    //SWAP
    int carry = heap[j/2];
    heap[j/2] = heap[j];
    heap[j] = carry;

      j /= 2;
  }
  return;
}

void REMOVEMIN()
{
  heap[1] = heap[heap.size()-1];
  heap.pop_back();

  int j = 1;

  while( ( 2*j < heap.size() &&  heap[j] > heap[2*j] ) || ( 2*j+1 < heap.size() && heap[j] > heap[2*j+1] ) )
  {
      if( 2*j+1 < heap.size() && heap[2*j] > heap[2*j+1] )
      {
       //SWAP
       int carry = heap[j];
       heap[j] = heap[2*j+1];
       heap[2*j+1] = carry;
       j = 2*j+1;
      }
      else
      {
       //SWAP
       int carry = heap[j];
       heap[j] = heap[2*j];
       heap[2*j] = carry;
       j = 2*j;
      }
  }
  return;
}

int GETMIN()
{
  return heap[1];
}

int n, a;

int main()
{
  ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);

  heap.push_back(-1);

  cin >> n;
 if( n % 2 == 0 )
 {
     int m = n/2 + 1;
      while(n--)
      {
         cin >> a;
         ADD(a);

        if( heap.size() - 1 > m )
        {
          REMOVEMIN();
        }
      }
  int mid1 = GETMIN();
  REMOVEMIN();
  int mid2 = GETMIN();
  bool f = 0;

  if( mid1 % 2 == 0 && mid2 % 2 == 0 )
    cout << mid1/2 + mid2/2;
  else if( ( mid1 % 2 == 1 && mid2 % 2 == 0 ) || ( mid1 % 2 == 0  && mid2 % 2 == 1 ) )
    cout << mid1/2 + mid2/2 << ".5";
  else
    cout << mid1/2 + mid2/2 + 1;
 }
 else
 {
     int m = n/2 + 1;
      while(n--)
      {
         cin >> a;
         ADD(a);
         if( heap.size() - 1 > m )
        {
          REMOVEMIN();
        }
      }
     cout << GETMIN();
 }


  return 0;
}
BUT WHY MLE? ?:'(

Edited by author 26.10.2019 00:08

Edited by author 26.10.2019 00:09

Edited by author 26.10.2019 00:09

Edited by author 26.10.2019 00:09