Untitled
unknown
plain_text
a year ago
4.6 kB
51
Indexable
Never
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; class Solution{ private final static int CMD_INIT = 1; private final static int CMD_ARRIVE = 2; private final static int CMD_LEAVE = 3; private final static UserSolution usersolution = new UserSolution(); private static boolean run(BufferedReader br) throws Exception { int q = Integer.parseInt(br.readLine()); int n, mid; int cmd, ans, ret =0; boolean okay = false; for (int i=0; i<q;i++){ StringTokenizer sr = new StringTokenizer(br.readLine(), " "); cmd = Integer.parseInt(st.nextToken()); switch(cmd){ case CMD_INIT: n = Integer.parseInt(st.nextToken()); usersolution.int(); okay=true; break; case CMD_ARRIVE: mid = Integer.parseInt(st.nextToken()); ans = Integer.parseInt(st.nextToken()); ret = Integer.parseInt(st.nextToken()); if(ret != ans) okay = true; break; case CMD_LEAVE: mid = Integer.parseInt(st.nextToken()); ans = Integer.parseInt(st.nextToken()); ret = Integer.parseInt(st.nextToken()); if(ret != ans) okay = true; break; default: okay = true; break; } } return okay; } public static void main(String[] args) throws Exception { int TC, MARK; System.setIn(new java.io.FileInputStream("sample_input.txt")); StringTokenizer st = new StringTokenizer(br.readLine(), " "); TC = Integer.parseInt(st.nextToken()); MARK = Integer.parseInt(st.nextToken()); for (int tc = 1; tc<= TC;tc++){ int score = run(br) ? MARK :0; System.out.println("#"+tc+" "+score); } br.close(); } } import java.util.*; class Node { int begin, end, size; Node (int b, int e){ this.begin = b; this.end = e; this.size = end-begin+1; } } class CmpSize implements Comparator<Node> { @Override public int compare(Node o1, Node o2){ if(o1.size == o2.size) return o1.begin-o2.begin; return o1.size-o2.size; } } class CmpBegin implements Comparator<Node> { @Override public int compare(Node o1, Node o2){ return o1.begin-o2.begin; } } class UserSolution{ private TreeSet<Node> treeSize; private TreeSet<Node> treeBegin; private HashMap<Integer, Integer> hashID; int N, empty; public void init(int N){ this.N = N; empty = N; treeSize = new TreeSet<Node>(new CmpSize); treeBegin = new TreeSet<Node>(new CmpBegin); Node n = new Node(1, N); treeSize.add(n); treeBegin.add(n); return; } public void arrive(int mId){ empty--; Node max = treeSize.poolFirst(); treeBegin.remove(max); int set = (max.begin+max.end) / 2; if(max.begin==1) set = 1; else if(max.end==N) set = N; if(set>max.begin){ Node temp = new Node(max.begin, set-1); treeBegin.add(temp); treeSize.add(temp); } if(set<max.begin){ Node temp = new Node(set+1,max.end); treeBegin.add(temp); treeSize.add(temp); } hashID.put(temp); return set; } public void leave(int mId){ empty++; int cut = hashID.remove(mId); Node tmp = new Node(cut,cut); Node tHight = treeBegin.higher(tmp); Node tLow = treeBegin.lower(tmp); if (tLow != null && tLow.end == cut-1){ treeSize.remove(tLow); treeBegin.remove(tLow); tmp.begin = tLow.begin; tmp.size = tmp.end-tmp.begin+1; } if (tHight != null && tHight.begin == cut+1){ treeSize.remove(tHight); treeBegin.remove(tHight); tmp.end = tHight.end; tmp.size = tmp.end-tmp.begin+1; } treeBegin.add(tmp); treeSize.add(tmp); return empty; } } 1 100 12 1 8 2 200 1 2 100 8 2 700 4 2 600 6 3 200 5 2 300 1 2 800 2 2 200 3 3 600 3 3 100 4 2 400 8