#include <iostream>

int main()
{
  int N;
  std:: cin >> N;
  /* dynamic memory allocation */
  int ** p = new int * [N];
  for (int i = 0; i < N; i++)
    p[i] = new int [N];

  /* initialize upper triangle matrix */
  p[0][N-1] = 1;
  int m, n;
  int ct = 1, value = 2, iter = 1, row = 0, column = N - 2;
  while (ct <= N - 1)
  {
    n = column, m = row;
    for (int i = 0; i <= iter; i++)
    {
      p[m++][n++] = value;
      value++;
    }

    iter++; ct++;
    column--;
  }

  /* initialize the lower triangle matrix */
  row = 1; column = 0, iter = N - 2;
  while (ct > 1)
  {
    n = column, m = row;
    for (int i = 0; i <= iter; i++)
    {
      p[m++][n++] = value;
      value++;
    }

    iter--; ct--;
    row++;
  }

  /* display matrix */
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
      std::cout << p[i][j] << " ";
    std::cout << std::endl;
  }

  /* release memory */
  for (int i = 0; i < N; i++)
    delete[] p[i];
  delete[] p;

  return 0;
}

first i get acces violation in my code. and then i search what it acces violation, and then i remake my code, then submit again. still get WA #4, before i reamke the code it says Accces Violation in test #4. Can anybody help me?

This is my code.

#include <iostream>
using namespace std;

int n,ar[10000],p;

int main(){
    cin>>n;
    for (int i=1;i<=n*n;i++){
        cin>>p;
        ar[p]=p;
    }
    for (int i=1;i<=n*n;i++){cout<<ar[i]<<' ';}
}

Edited by author 15.07.2017 10:58

tried all mentioned test cases .all correct. still WA on #12.
using surfix array.any idea?

code here:

#include <cstdio>
#include <cstring>
int const N=220000;
int st[256], rank[2*N], rank1[2*N], count[N], tmp[N];
char a[N], b[N], s[N], max1;
int sa[N], height[N], si;
int main(){
    memset(st, 0, sizeof st);
    memset(rank, 0, sizeof rank);
    memset(rank1, 0, sizeof rank1);
    scanf("%s", b);
    int n1=strlen(b);
    for(int i=1; i<=n1; ++i)a[i]=b[i-1];
    for(int i=1; i<=n1; ++i)a[i+n1+1]=b[n1-i];
    a[0]=' ';
    a[n1+1]='#';
    int n=2*n1+1;
    a[n+1]='&';
    for(int i=1; i<=n; ++i)st[a[i]]=1;
    for(int i=1; i<=255; ++i)st[i]+=st[i-1];
    for(int i=1; i<=n; ++i)rank[i]=st[a[i]];

    int k=0;
    for(int p=1; k!=n; p+=p){
        memset(count, 0, sizeof count);
        for(int i=1; i<=n; ++i)count[rank[i+p]]++;
        for(int i=1; i<=n; ++i)count[i]+=count[i-1];
        for(int i=n; i>=1; --i)tmp[count[rank[i+p]]--]=i;

        memset(count, 0, sizeof count);
        for(int i=1; i<=n; ++i)count[rank[i]]++;
        for(int i=1; i<=n; ++i)count[i]+=count[i-1];
        for(int i=n; i>=1; --i)sa[count[rank[tmp[i]]]--]=tmp[i];

        memcpy(rank1, rank, sizeof rank1);
        rank[sa[1]]=k=1;
        for(int i=2; i<=n; ++i){
            if(rank1[sa[i]]!=rank1[sa[i-1]] or rank1[sa[i]+p]!=rank1[sa[i-1]+p])++k;
            rank[sa[i]]=k;
        }
    }
    k=0;
    for(int i=1; i<=n; ++i){
        if(rank[i]==1){
            k=0;
        }else{
            --k;
            if(k<0)k=0;
            while(a[i+k]==a[sa[rank[i]-1]+k])++k;
        }
        height[rank[i]]=k;
    }

    int max=-1;
    for(int i=2; i<=n; ++i){
        int p=sa[i];
        int q=sa[i-1];
        if((p-1)/n1 != (q-1)/n1){
            if(p+q+height[i]==n+2){
                if(height[i]>max){
                    max=height[i];
                    si=p;
                }
            }
        }
    }
    for(int i=si; i<si+max; ++i)printf("%c", a[i]);
    return 0;
}

THX :)

How is that possible that SASUKE UCHIHA got compilation error??
http://imgur.com/BB0osSN

#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
#define INF (1e9+7)
#define forn(i,z,n) for( auto (i) = (z); (i) < (n); ++i)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

struct node {
    int key;
    node *left, *right, *parent;
    node(int q, node *x, node *y, node *p)  {
        key = q;
        left = x;
        right = y; parent = p;
    }
};
node *tree  = NULL, *f = NULL;
void add_n( node *j, node *&z)  {
    if( z == NULL)  {
        z = new node(j->key,NULL,NULL,NULL);
        return ;
    }
    if( z->key >= j->key)  {
        if( z->left)  {
            add_n(j, z->left);
        }
        else  {
            z->left = j;
            j->parent = z;
        }
    }
    else  {
        if( z->right)  {
            add_n(j,z->right);
        }
        else  {
            j->parent = z;
            z->right = j;
        }
    }
}
void show( node *x)  {
    if( x != NULL)  {
        show(x->left);
        cout << x->key << ' ';
        show(x->right);
    }
    else return ;
}
node *find_min( node *root)  {
    if( root->left != NULL)  {
        return find_min(root->left);
    }
    else  {
        return root;
    }

}
void delete_n(node *root, int val )  {
    if( root == NULL)  return ;
    else if( val < root->key)  delete_n( root->left, val);
    else if( val > root->key) delete_n(root->right, val);
    else  {
        if( root->left == NULL && root->right ==NULL)  {
            //delete root;
            root = NULL;
        }
        else if( root->left == NULL)  {
            root->right->parent = root->parent;
            root = root->right;
            //delete root->right;
            root->right = NULL;
        }
        else if( root->right == NULL)  {
            root->left->parent = root->parent;
            root = root->left;
            //delete root->left;
            root->left = NULL;
        }
        else  {
            node *temp = find_min( root->right);
            temp->parent = root->parent;
            root = temp;
            delete_n( root->right, temp->key);
        }
    }
    return ;
}
void post( node *x)  {
    if( x != NULL)  {
        post(x->right);
        post(x->left);
        cout << x->key << ' ';
    }
}
void show_parents( node *z)  {
    if(z != NULL)  {
        show_parents(z->left);
        show_parents(z->right);
        if( z->parent != NULL)
            cout << z->key << ' ' <<  (z->parent->key) << endl;
    }
}
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector <int> v;
    forn(i,0, n)  {
        int x;
        cin >> x;
        v.pb(x);
    }
    for(int i = 0; i <n; ++i)  {
        node *help = new node(v[i], NULL, NULL,NULL);
        add_n( help, tree);
    }
    show(tree);                              // в невозрастающем порядке
    delete_n(tree, 3);
    cout << endl;
    show(tree);
    return 0;
}

#include<iostream>
#include<string>
using namespace std;
int main ()
{
    string s;
    cin>>s;
    int max=0,i=0,index=0,a=0,p=0;
    for (i=0; i<s.size()-5; i++)
    {
    if(s[i]>'a' && s[i]<='z')
    p--;
    if(s[i]=='S')
    p+=2;
    if(s[i+1]=='a')
     p+=2;
    if(s[i+1]>='A' && s[i+1]<='Z')
     p--;
    if(s[i+2]=='n')
    p+=2;
    if(s[i+2]>='A' && s[i+2]<='Z')
    p--;
    if(s[i+3]=='d')
    p+=2;
    if(s[i+3]>='A' && s[i+3]<='Z')
    p--;
    if(s[i+4]=='r')
    p+=2;
    if(s[i+4]>='A' && s[i+4]<='Z')
    p--;
    if(s[i+5]=='o')
    p+=2;
    if(s[i+5]>='A' && s[i+5]<='Z')
     p--;
        if (p>max)
        {
            max=p;
            index=i;
        }
        p=0;
            }
    i=index;
    if (s[i]!='S' && s[i]>='A' && s[i]<='Z' || s[i]=='s')
    a+=5;
    else if (s[i]!='S' && s[i]>='a' && s[i]<='z')
    a+=10;
    if (s[i+1]!='a' && s[i+1]>='a' && s[i+1]<='z' || s[i+1]=='A')
    a+=5;
    else if (s[i+1]!='a' && s[i+1]>='A' && s[i+1]<='Z')
    a+=10;
    if (s[i+2]!='n' && s[i+2]>='a' && s[i+2]<='z' || s[i+2]=='N')
    a+=5;
    else if (s[i+2]!='n' && s[i+2]>='A' && s[i+2]<='Z')
    a+=10;
    if (s[i+3]!='d' && s[i+3]>='a' && s[i+3]<='z' || s[i+3]=='D')
    a+=5;
    else if (s[i+3]!='d' && s[i+3]>='A' && s[i+3]<='Z')
    a+=10;
    if (s[i+4]!='r' && s[i+4]>='a' && s[i+4]<='z' || s[i+4]=='R')
    a+=5;
    else if (s[i+4]!='r' && s[i+4]>='A' && s[i+4]<='Z')
    a+=10;
    if (s[i+5]!='o' && s[i+5]>='a' && s[i+5]<='z' || s[i+5]=='O')
    a+=5;
    else if (s[i+5]!='o' && s[i+5]>='A' && s[i+5]<='Z')
    a+=10;
    cout<<a<<endl;
    return 0;
}

Edited by author 30.12.2014 18:40

Edited by author 03.01.2015 17:13

Edited by author 03.01.2015 17:13

1)Look at my solution 7450309 (Runtime error (non-zero exit code) on test 23)) and 7450312(AC). Why i got Runtime error (non-zero exit code) on test 23?
  In first solution i have nmax=123456 and in second 223456. What is range of n?

2)Look on problem 1974. In forum i wrote test when my AC solution get wrong answer(I can write more tests where my old AC solution falls)

I have solved it by reduction to a graph exploration task.
Each vertex consists of three parameters (i, j, pr).
Where i, j denote number of card at the top of each pile and pr denotes previous state.  pr is also a "used"  array.  So,  if pr[N] [N] =none,  then impossible.  Otherwise  just recover answer using pr.  You can also have in your state additional parameter diff denotes difference between red and black cards.  I have used instead additional two arrays diff11 and diff2 denote difference between first i cards in first pile and in the second pile respectively.  There is an edge iff difference at the next step would be not greater than one (abs) ,  obviously.

//I have correct in the IDE, what's wrong?

import java.io.IOException;
import java.util.Scanner;

public class VasyaCare{
    public static void main(String[] args) throws IOException {
    VasyaCare vasya_care = new VasyaCare();
    Scanner scn = new Scanner(System.in);
    int n = scn.nextInt();
    try{                               // Check
            if(n < 10){
        double[] b = vasya_care.setScore(n);
        double median = vasya_care.getMedian(b);
        if(median==3){
            System.out.println("None");
        }
        else if(median==5){
            System.out.println("Named");
        }
        else if(median >= 4.5){
            System.out.println("High");
        }
        else if(median < 4.5){
            System.out.println("Common");
        }
        }
        else throw new IOException("Please, type number from 1 to 10!");
    }
    catch(Exception e){e = new IOException();}
    }


    double getMedian(double[] b{          // calculate median score of exam
    int sum = 0;
    for(int i = 0; i < b.length; i++){
        sum = (int) (sum + b[i]);
    }
    return (double)sum/b.length;
    }

    double[] setScore(int n){            // forming list scores
    Scanner scn = new Scanner(System.in);
    double[] b = new double[n];{
        for(int j = 0; j < n; j++){
            int m = scn.nextInt();
            if(m<3 || m > 5){
                System.out.println("Type score from 3 to 5: ");
                j--;
            }
            else if (m>=3 && m<=5){
                b[j] = m;
            }
        }
    }
    return b;
    }
}

// Thank you for your attention!

Let unsigned long long total_cost=0.
For every edge E in tree total_cost +=cost_of_all_paths_lies_on_edge(E).
double ans=2.0*total_cost/n/(n-1) is overflow and and WA#19.
================
Let double ans = 0.
For every edge E in tree ans+=2.0*cost_of_all_paths_lies_on_edge(E)/n/(n-1).
That is AC.
===========
Maybe if not multiply by two in the first scenario there is also AC,  I have not tested.

Could anyone help me?

5
AAAAA
ans:5.000

6
CBDCBD
ans:3.600

6
DDADDD
ans:2.000
They helped me to solve this problem~
Hope they can help you
o(∩_∩)o...

0-1 bfs on graph with 2 * n verticles.

how to solve this problem?
construct suffix tree for N times and then LCP or there is easier and faster way?

Is it possible to solve this problem using suffix automata? I got TL5.
But I think that O(N * K) solution have to work faster. Am I wrong? Thanks.

PS. Got AC with KMP O(N * K).

Edited by author 26.08.2015 00:30

//#define LOCAL
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 250000+10

int N;
char str1[MAXN], str2[MAXN];
char temp[MAXN*2];

int kmp(char* s, char* t, int pos);
void get_next(char* t, int* next, int t_len);
int main()
{
#ifdef LOCAL
    freopen("1423_String_Tale_2.in", "r", stdin);
    freopen("1423_String_Tale_2.out", "w", stdout);
#endif

    scanf("%d", &N);
    scanf("%s%s", str1, str2);

    int s1_len = strlen(str1);
    int s2_len = strlen(str2);

    if(s1_len != s2_len){
        printf("%d\n", -1);
        return 0;
    }

    strcpy(temp, str1);
    strcat(temp, str1);
    int ans;
    ans = kmp(temp, str2, 0);
    if(ans != 0 && ans != -1)
        printf("%d\n", s1_len-ans);
    else
        printf("%d\n", ans);

    return 0;
}

int kmp(char* s, char* t, int pos)
{
    int s_len = strlen(s);
    if(pos<0 || pos>s_len-1){
        fprintf(stderr, "%s", "Error: invalid pos.");
        system("pause");
    }

    int t_len = strlen(t);
    int *next = (int*)malloc(sizeof(int) * t_len);
    get_next(t, next, t_len);

    int i = pos;
    int j = 0;

    while(i<s_len && j<t_len){
        if(j<0 || s[i]==t[j]){
            i++;
            j++;
        }
        else
            j = next[j];
    }

//    free(next);
    if(j >= t_len)
        return i-t_len;
    else
        return -1;
}

void get_next(char* t, int* next, int t_len)
{
    next[0] = -1;
    int j = 0;
    int k = -1;
    while(j < t_len){
        if(k==-1 || t[j]==t[k]){
            j++;
            k++;
            next[j] = k;
        }
        else
            k = next[k];
    }
}

###############################################
Can anyone tell me WHY???

Edited by author 11.07.2017 19:31

Please, give me some hints on how to solve it. Thanks in advance.

I have got a verdict Compiler Failed on Clang compiler.  Never have got such a verdict.  Every other compiler submit gets AC. Can't post code here because it is a working solution.

I was trying to do the following.
Construct suffix automation for each command.
Binary search for length of each key substring.
Binary search works as follows.
For each substring of command of len (lower_bound+upper_bound) /2 check whether it is a substring of another command.