ericdai1's blog

By ericdai1, history, 7 weeks ago, In English

Problem

Here's my code that I assume works correctly, however, it keeps giving my a Time Limit Exceeded despite it being O(n*t), which makes me confused. I have tried making it faster using stringbuilder, bufferedReader, etc. but none of it worked.

package thread;
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException
	{
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		//long startTime = System.nanoTime();
		int t = sc.nextInt();
		for (int i = 0; i < t; i++)
		{
			int len = sc.nextInt();
			String bin = sc.next();
			char[] digits = bin.toCharArray();
			ArrayList<Integer> flags = new ArrayList<>();
			int subs = 0;
			StringBuilder sB = new StringBuilder("");
			
			for (int j = 0; j < len; j++)
			{
				if (digits[j] == '0')
				{
					if (flags.contains(0))
					{
						int c = flags.indexOf(0);
						sB.append(c+1);
						sB.append(" ");
						flags.set(c, 1);
					}
					else
					{
						flags.add(1);
						sB.append(flags.size());
						sB.append(" ");
						subs++;
					}
				}
				else if (digits[j] == '1')
				{
					if (flags.contains(1))
					{
						int c = flags.indexOf(1);
						sB.append(c+1);
						sB.append(" ");
						flags.set(c, 0);
					}
					else
					{
						flags.add(0);
						sB.append(flags.size());
						sB.append(" ");
						subs++;
					}
				}
			}
			pw.println(subs);
			
			pw.println(sB);
		}
		//long elapsedTime = System.nanoTime() - startTime;
		//pw.println(elapsedTime/1000000);
		pw.close();
		
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	
	
}

I would appreciate any advice or a tutorial (if any of you participated in today's Div. 3 contest and solved it that would be great). Thanks!

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Indexof is linear

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you have any recommendations on what to replace it with?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try to change your whole solution and use binary search.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I suggest you keep track of '0's and '1's separately (e.g. have separate ArrayLists for them). You could do binary search, but I believe it's overkill here, especially for a div. 3 D problem for which it isn't the main algo. So yeah, two lists, one for the last 0s, the other for the last 1s.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Check out this solution.