10098 - Generating Fast

[qwerfv]

Thanks to chunyi81 and tywok's advice
I realized what's wrong and........
I get AC now....

[Backbone]

Hi!!!, ahm i hope that anybody here can help me! I got TLE for this Prob, and I don't know where is my error!!! Thanks in advance!!!

Code: Select all

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

using namespace std;

int main()
{
int n;
string linea;
scanf("%d",&n);
fflush(stdin);
 while(n--)
  {
  getline(cin,linea);
  sort(linea.begin(),linea.end()-1); 
    do
    cout<<linea<<endl;                 
    while(next_permutation( linea.begin(),linea.end() ));
  cout<<endl;
  }
}

[algoJo]

I thought I'm right...
but the judges said WA...
can anybody post some critical i/o set??
thanks before..
and is this i/o set are correct?
INPUT

Code: Select all

3
ACba
AcB
bCA

OUTPUT

Code: Select all

ACab
ACba
AaCb
AabC
CAab
CAba
CaAb
CabA
CbAa
CbaA
aACb
aAbC
aCAb
aCbA
abAC
abCA
bACa
bAaC
bCAa
bCaA
baAC
baCA

ABc
AcB
BAc
BcA
cAB
cBA

ACb
AbC
CAb
CbA
bAC
bCA

[Jan]

Your output is not correct, because for 'ACba' you have a total of 4! = 24 permutations. But your output has 22 of them. And the permutations are

Output:

Code: Select all

ACab
ACba
AaCb
AabC
AbCa
AbaC
CAab
CAba
CaAb
CabA
CbAa
CbaA
aACb
aAbC
aCAb
aCbA
abAC
abCA
bACa
bAaC
bCAa
bCaA
baAC
baCA

Hope it helps.

[rezaeeEE]

i get PE in this problem.

can any body help me

Code: Select all

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

char st[10];
string s;



int main()
{
    int n;
    cin>>n;
    string s;
    
    for(int N=0;N<n;N++)
    {
    cin>>s;
    
    for(int i=0;i<s.length();i++)
            st[i]=s[i];
    
    sort(st,st+s.length());   
    
    for(int i=0;i<s.length();i++)
     printf("%c",st[i]);
     
     printf("\n");
    
    while(next_permutation(st,st+s.length()))
    {
    for(int i=0;i<s.length();i++)
    printf("%c",st[i]);
    printf("\n");
    }
    
    if(N<n-1)
             printf("\n");
    
    }
    
    return 0;
}

thanks

[tgoulart]

There must be a blank line after the last set too.

[Zvid]

I'm getting TLE in this problem. Can anyone help me?

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main () {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        string s;
        cin >> s;
        sort(s.begin(),s.end());
        do {
            cout << s << endl;
        } while (next_permutation(s.begin(),s.end()));
        cout << endl;
    }
}

[mf]

iostreams are quite slow. Use scanf/printf instead cin and cout.

[GUC.HassanMohamed]

Hello everbody,

I have passed this problem using C++ after getting TLE when trying to take the IO using cin-cout
and I tried to pass it with java (my default language) but I can't and I think the problem is in the I/O
specially for the output as outputting 10! lines (3628800) requires efficient IO.
However, I have seen many people passing it with java so any suggestions for the IO?

Thanks in advance.

[GUC.HassanMohamed]

Hello everybody,

I am having difficulties solving some problems using Java (TLE) but it passes after reimplementing it in C++
like (http://icpcres.ecs.baylor.edu/onlinejud ... oblem=1039) and I am pretty sure that this issue concerns the IO so I wonder if anybody could help me to enhance my IO efficiency.

Any help would be appreciated.

Here is my solution to the problem I mentioned using Java:

Code: Select all

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args)throws IOException {
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		int times = new Integer(br.readLine());
		String in;
		for(int i  = 0; i < times;i++){
			in = br.readLine();
			if(i != 0)
				System.out.println("");
			char [] ch = in.toCharArray();
			Arrays.sort(ch);
			System.out.write((new String(ch)+"\n").getBytes());
			while(j_next_permutation(ch))
				System.out.write((new String(ch)+"\n").getBytes());
		}
	}
	public static boolean j_next_permutation(char [] a) {
		int F = 0, L = a.length, I = a.length;
		if (F == L || F == --I) return false;
		for (;;) {
			int Ip = I;
			if (a[--I] < a[Ip]) {
				int J = L;
				for (; !(a[I] < a[--J]););
				char tmp = a[I]; a[I] = a[J]; a[J] = tmp;
				for (int i = Ip; i < ((L - Ip) % 2 == 0 ? Ip + (L - Ip) / 2 : Ip + (L - Ip) / 2 + 1); ++i) {
					char tm = a[i]; a[i] = a[a.length - 1 - i + Ip]; a[a.length - 1 - i + Ip] = tm;
				}
				return true;
			}
			if (I == F) {
				for (int i = 0; i < ((L - F) % 2 == 0 ? (L - F) / 2 : (L - F) / 2 + 1); ++i) {
					int tm = a[i]; a[i] = a[a.length - 1 - i]; a[a.length - 1 - i] = a[i];
				}
				return false;
			}
		}
	}
}

[lnr]

To GUC.HassanMohamed

Taking input seems alright to me.
May be taking input in java is slower than C or C++.

[abhiramn]

Code: Select all

#include<stdio.h>
char temp[12];
int arr[130],len;
void perm(int index)
{
	int i;
	if(index==len)
	{
		printf("%s\n",temp);
		return;
	}
	for(i=47;i<124;++i)
		if(arr[i])
		{
			temp[index]=i;
			--arr[i];
			perm(index+1);
			++arr[i];
		}
}
int main()
{
	int n,i,t=0;
	char ch;
	for(scanf("%d%*c",&n);n--;)
	{
		for(i=47;i<124;arr[i]=0,++i);
		for(len=0;(ch=getchar())!='\n';++arr[ch],++len);
		temp[len]='\0';
		if(t)
			putchar('\n');
		else
			t=1;
		perm(0);
	}
	return 0;
}

My program gives correct output for all the test cases on the forum. Still, I am getting a WA. Please help.

[dodouuu]

if(t)
putchar('\n');
else
t=1;

these four lines delete and put printf("\n"); below perm(0); just like


perm(0);
printf("\n");

[uDebug]

Replying to follow the thread.

[sajal2k8]

Here is my code:
#include <iostream>
#include<algorithm>

using namespace std;

int main()
{
int a,b=0,c;
string str[10000],s,q,r;
char ch;
cin>>a;
for(int i=0;i<a;i++)
{
cin>>s;
for(int k=0;k<s.length()-1;k++)
{
for(int l=k+1;l<s.length();l++)
{
if(s[k]>s[l])
{
ch=s[l];
s[l]=s[k];
s[k]=ch;
}
}
}
do
{

str=s;
b++;

}while(std::next_permutation(s.begin(),s.end()));
sort(str,str+b);
for(int j=0;j<b;j++)
{
cout<<str[j]<<endl;
}
if(i!=a-1)
cout<<endl;
b=0;
}
return 0;
}
I am getting runtime error. Please help. Thank You in advance.