Rezultati

Up. imeNalogaJezikRezultatČas oddaje
scnm1-2018 Prehitevanje Java 100/100OK 04. okt '18 @ 16:40

Test Točke Porabljen spomin Porabljen čas Status
#1 16/16 35,160 MiB 0,000 s OK
#2 16/16 34,941 MiB 0,000 s OK
#3 17/17 36,988 MiB 0,000 s OK
#4 17/17 99,566 MiB 0,471 s OK
#5 17/17 143,801 MiB 0,000 s OK
#6 17/17 34,293 MiB 0,000 s OK

Ocenjevani program (n1.java):
import java.util.*;
import java.io.*;

public class n1 {

	public static void main(String[] args) throws Exception{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(in.readLine());
		HashMap<String,Integer> hm=new HashMap<String,Integer>();
		HashMap<Integer,String> hmr=new HashMap<Integer,String>();
		for(int i=0;i<n;i++) {
			String s=in.readLine();
			hm.put(s, i);
			hmr.put(i, s);
		}
		int[]prev=new int[n];
		int[]next=new int[n];
		for(int i=0;i<n-1;i++) {
			next[i]=i+1;
		}
		next[n-1]=-1;
		for(int i=1;i<n;i++) {
			prev[i]=i-1;
		}
		prev[0]=-1;
		int q=Integer.parseInt(in.readLine());
		for(int i=0;i<q;i++) {
			StringTokenizer st=new StringTokenizer(in.readLine());
			int tm=hm.get(st.nextToken());
			int place=hm.get(st.nextToken());
			if(tm==place||prev[place]==tm) {
				continue;
			}
			int l1=prev[tm];
			int r1=next[tm];
			int l2=prev[place];
			int r2=next[place];
			if(l1==-1) {
				prev[r1]=-1;
				//nexta ni
			}else if(r1==-1) {
				//preva ni
				next[l1]=-1;
			}else {
				next[l1]=r1;
				prev[r1]=l1;
			}
			prev[place]=tm;
			next[tm]=place;
			if(l2==-1) {
				prev[tm]=-1;
			}else if(r2==-1) {
				//ok?
				prev[tm]=l2;
				next[l2]=tm;
			}else {
				prev[tm]=l2;
				next[l2]=tm;
			}
//			
//			int[]ans=new int[n];
//			int start=-1;
//			for(int qq=0;qq<n;qq++) {
//				if(prev[qq]==-1) {
//					start=qq;
//				}
//			}
//			for(int qq=0;qq<n;qq++) {
//				ans[qq]=start;
//				start=next[start];
//			}
//			for(int qq:ans) {
//				System.out.println(hmr.get(qq));
//			}
			
		}
		int[]ans=new int[n];
		int start=-1;
		for(int qq=0;qq<n;qq++) {
			if(prev[qq]==-1) {
				start=qq;
			}
		}
		for(int qq=0;qq<n;qq++) {
			ans[qq]=start;
			start=next[start];
		}
		for(int i:ans) {
			System.out.println(hmr.get(i));
		}
	}

}