Pat(Basic Level)Practice--1025(チェーンテーブルを反転)

Pat 1025コード
タイトルの説明:
定数Kと単一チェーンテーブルLを指定するには、プログラムを記述してLの各Kノードを反転します.例えば、Lが1→2→3→4→5→6、Kが3であれば、出力は3→2→1→6→5→4であるべきである.Kが4の場合、出力は4→3→2→1→5→6であるべきであり、すなわち最後にK個未満の要素は反転しない.
入力形式:
各入力には1つのテスト例が含まれています.各試験例1行目には、1番目のノードのアドレス、ノードの合計個数の正の整数N(<=105)、および正の整数K(<=N)、すなわち、反転が要求されるサブチェーンノードの個数が与えられる.ノードのアドレスは5ビットの非負の整数であり,NULLアドレスは−1で表される.
次に、N行があります.各行のフォーマットは次のとおりです.
Address Data Next
ここでAddressはノードアドレスであり、Dataはそのノードに格納された整数データであり、Nextは次のノードのアドレスである.
出力フォーマット:
各テスト例に対して、反転したチェーンテーブルが順次出力され、その上の各ノードは1行を占め、フォーマットは入力と同じである.
サンプルを入力:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

出力サンプル:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

コード:

#include<cstdio>
#include<cstring>
#include<vector>
#define MAX 100001

using namespace std;

typedef struct Node
{
	char addr[6];
	int data;
	char next[6];
}Node;

int visited[MAX];

int main(int argc,char *argv[])
{
	int n,k;
	int index,i,j;
	char first[6];
	vector<Node> v;
	Node N[MAX];
	scanf("%s %d %d",first,&n,&k);
	for(i=0;i<n;i++)
		scanf("%s %d %s",N[i].addr,&N[i].data,N[i].next);
    for(i=0;i<n;i++)
		if(strcmp(N[i].addr,first)==0)
		{
			index=i;
			break;
		}
	for(i=0;i<n;i++)
	{
		v.push_back(N[index]);
		visited[index]=1;
		for(j=0;j<n;j++)
			if(visited[j])
				continue;
			else
			{
				if(strcmp(N[index].next,N[j].addr)==0)
				{
					index=j;
					break;
				}
			}
	}
	int loop=n/k;
	for(i=1;i<=loop;i++)
	{
		j=i*k;
		for(int m=1;m<=k;m++)
		{
			if(i<loop&&n%k==0&&m==k)
				strcpy(v[j-1].next,v[(i+1)*k-1].addr);
			else if(i==loop&&m==k)
			{
				if(n%k==0&&i==loop)
					strcpy(v[j-1].next,"-1");
				else if(n%k!=0)
					strcpy(v[j-1].next,v[loop*k].addr);
			}
			else
				strcpy(v[j-1].next,v[j-2].addr);
		    printf("%s %d %s
",v[j-1].addr,v[j-1].data,v[j-1].next);
		    j--;
		}
	}
	for(i=loop*k;i<n;i++)
		printf("%s %d %s
",v[i].addr,v[i].data,v[i].next);

	return 0;
}

ええ、1つのcaseがタイムアウトして、1つのcaseが間違って、もっと良い解題方法を求めます!!!
最近ある人は私に教えて、最後のcaseはいくつかの無効なノードを含んで、最後にコードを変更してACになりました.の
実は上のような方法を続けて、最後から2番目のcaseがタイムアウトして、結局O(n*n)の複雑さで、最後にO(n)の複雑さでチェーンテーブルをつなぐ方法を考えました.チェーンテーブルをリンクしなくてもACは可能なので、1階の方法を参照してください.(PS:Pat太坑..)
ACコード:

#include<cstdio>
#include<vector>
#define MAX 100005

using namespace std;

typedef struct Node
{
	int addr;
	int data;
	int next;
}Node;

typedef struct Data
{
	int data;
	int next;
}Data;

int main(int argc,char *argv[])
{
	int n,k,cur;
	int index,i,j;
	int first;
	vector<Node> v(MAX);
	Data D[MAX];
	scanf("%d %d %d",&first,&n,&k);
	for(i=0;i<n;i++)
	{
		int addr,data,next;
		scanf("%d %d %d",&addr,&data,&next);
		D[addr].data=data;
		D[addr].next=next;
	}
	int size=0;
	cur=first;
	while(1)//      
	{
		Node temp;
		temp.addr=cur;
		temp.data=D[cur].data;
		temp.next=D[cur].next;
		v[size]=temp;
		size++;
		if(D[cur].next==-1)
			break;
		cur=D[cur].next;
	}
	int loop=size/k;
	for(i=1;i<=loop;i++)//  
	{
		j=i*k-1;
		for(int m=1;m<=k;m++)
		{
			if(i<loop&&m==k)//     K   ，   1 2 3 4 5 6 7 ，k=3
				v[j].next=v[(i+1)*k-1].addr;//     1  6
			else if(i==loop&&m==k)
			{
				if(size%k==0)//            ，next -1
					v[j].next=-1;
				else//        ，next         
					v[j].next=v[loop*k].addr;
			}
			else
				v[j].next=v[j-1].addr;//  ， next       
			if(v[j].next==-1)
			printf("%05d %d %d
",v[j].addr,v[j].data,v[j].next);
			else
			printf("%05d %d %05d
",v[j].addr,v[j].data,v[j].next);
		    j--;
		}
	}
	for(i=loop*k;i<size;i++)
		if(v[i].next==-1)
			printf("%05d %d %d
",v[i].addr,v[i].data,v[i].next);
		else
			printf("%05d %d %05d
",v[i].addr,v[i].data,v[i].next);

	return 0;
}