Time Limit keeps getting exceeded. Division C Problem D

Revision en1, by ericdai1, 2020-08-05 19:57:00

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!

Tags help, div.3, time limit exceeded, #tle

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ericdai1 2020-08-05 19:57:00 2518 Initial revision (published)