#391481 (Java) No.910 素数部分列

• 問題: No.910 素数部分列
• ユーザー: kitakitalily
• 提出日時: 2019-10-18 23:23:15
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 321 ms / 1,000 ms
• コード長: 5,057 bytes
• コンパイル時間: 2,636 ms
• コンパイル使用メモリ: 78,804 KB
• 実行使用メモリ: 49,632 KB
• 最終ジャッジ日時: 2024-06-25 21:55:22
• 合計ジャッジ時間: 13,744 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 50

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
import java.util.*;
import java.io.*;
public class Main {
    static long mod = 998244353;
    static int INF = 1000000000;
    public static void main(String[] args){
        FastScanner scanner = new FastScanner();
        int n = scanner.nextInt();
        String s = scanner.next();
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(s.charAt(i) == '3' ||s.charAt(i) == '5' || s.charAt(i) == '7'){
                ans++;
            }
        }
        PriorityQueue<Integer> one = new PriorityQueue<Integer>();
        PriorityQueue<Integer> nine = new PriorityQueue<Integer>();
        for(int i = 0; i < n; i++){
            if(s.charAt(i) == '1'){
                one.add(i);
            }else if(s.charAt(i) == '9'){
                nine.add(i);
            }
        }
        int remn = 0;
        while(!one.isEmpty() && !nine.isEmpty()){
            int onetop = one.peek();
            int ninetop = nine.peek();
            if(ninetop < onetop){
                nine.poll();
                remn++;
            }else if(onetop < ninetop){
                one.poll();
                nine.poll();
                ans++;
            }
        }
        int a = one.size();
        int b = remn;
        while(a >= 1 && b >= 2){
            a -= 1;
            b -= 2;
            ans++;
        }
        ans += a/2;
        System.out.println(ans);
    }
    static class BIT{
        int n;
        int[] bit;
        public BIT(int n){
            this.n = n;
            bit = new int[n+1];
        }
        void add(int idx, int val){
            for(int i = idx+1; i <= n; i += i&(-i)) bit[i-1] += val;
        }
        int sum(int idx){
            int res = 0;
            for(int i = idx+1; i > 0; i -= i&(-i)) res += bit[i-1];
            return res;
        }
        int sum(int begin, int end){
            if(begin == 0) return sum(end);
            return sum(end)-sum(begin-1);
        }
    }
    static class Pair implements Comparable<Pair>{
    int first, second;
    Pair(int a, int b){
        first = a;
        second = b;
    }
    @Override
    public boolean equals(Object o){
        if (this == o) return true;
        if (!(o instanceof Pair)) return false;
        Pair p = (Pair) o;
        return first == p.first && second == p.second;
    }
    @Override
    public int compareTo(Pair p){
        //return first == p.first ? second - p.second : first - p.first; //firstで昇順にソート
        //return (first == p.first ? second - p.second : first - p.first) * -1; //firstで降順にソート
        //return second == p.second ? first - p.first : second - p.second;//secondで昇順にソート
        //return (second == p.second ? first - p.first : second - p.second)*-1;//secondで降順にソート
            //return first * 1.0 / second > p.first * 1.0 / p.second ? 1 : -1; // first/secondの昇順にソート
            //return first * 1.0 / second < p.first * 1.0 / p.second ? 1 : -1; // first/secondの降順にソート
                //return second * 1.0 / first > p.second * 1.0 / p.first ? 1 : -1; // second/firstの昇順にソート
            //return second * 1.0 / first < p.second * 1.0 / p.first ? 1 : -1; // second/firstの降順にソート
                //return Math.atan2(second, first) > Math.atan2(p.second, p.first) ? 1 : -1; // second/firstの昇順にソート
                //return first + second > p.first + p.second ? 1 : -1; //first+secondの昇順にソート
                //return first + second < p.first + p.second ? 1 : -1; //first+secondの降順にソート
                //return first - second < p.first - p.second ? 1 : -1; //first-secondの降順にソート
                return Math.atan2(second,first) > Math.atan2(p.second, p.first) ? 1 : -1;
        }
  }
    private static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
                if (ptr < buflen) {
                        return true;
                }else{
                        ptr = 0;
                        try {
                                buflen = in.read(buffer);
                        } catch (IOException e) {
                                e.printStackTrace();
                        }
                        if (buflen <= 0) {
                                return false;
                        }
                }
                return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
        public String next() {
                if (!hasNext()) throw new NoSuchElementException();
                StringBuilder sb = new StringBuilder();
                int b = readByte();
                while(isPrintableChar(b)) {
                        sb.appendCodePoint(b);
                        b = readByte();
                }
                return sb.toString();
        }
        public long nextLong() {
                if (!hasNext()) throw new NoSuchElementException();
                long n = 0;
                boolean minus = false;
                int b = readByte();
                if (b == '-') {
                        minus = true;
                        b = readByte();
                }
                if (b < '0' || '9' < b) {
                        throw new NumberFormatException();
                }
                while(true){
                        if ('0' <= b && b <= '9') {
                                n *= 10;
                                n += b - '0';
                        }else if(b == -1 || !isPrintableChar(b)){
                                return minus ? -n : n;
                        }else{
                                throw new NumberFormatException();
                        }
                        b = readByte();
                }
        }
        public int nextInt() {
                long nl = nextLong();
                if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
                return (int) nl;
        }
        public double nextDouble() { return Double.parseDouble(next());}
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX