#916741 (Java21) No.2486 Don't come next to me

提出ソース
結果

問題	No.2486 Don't come next to me
ユーザー	Asahi
提出日時	2023-09-29 23:13:49
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	13,531 bytes
コンパイル時間	5,536 ms
コンパイル使用メモリ	102,044 KB
実行使用メモリ	54,256 KB
最終ジャッジ日時	2024-07-22 17:11:58
合計ジャッジ時間	8,816 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	70 ms 38,044 KB
testcase_21	AC	71 ms 38,004 KB
testcase_22	AC	69 ms 38,124 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import java.util.*; 
import java.io.*;
import java.lang.reflect.Array;
import java.math.*; 
// import java.util.stream.*;
// import java.security.SecureRandom;

class Main implements Runnable
{ 
    record Tuple(long left , long right , long segment){ }
    //　区間の長さが偶数か1だと定まらない
    void solve()
    {           
        long N = in.nextLong() ;
        int M = in.nextInt();
        long [] seat = in.LongArray(M);
        ArrayList<Long> SEAT = new ArrayList<>();
        PriorityQueue<Tuple> Q = new PriorityQueue<>(
            Comparator.comparing(Tuple::segment , Comparator.reverseOrder())
        ){};
        long L = 0 , R = N + 1 ;
        long l = seat[0] - L - 1 , r = R - seat[M - 1] - 1 ;
        if(l > 1 && l % 2 == 1) SEAT.add(1L);
        if(r > 1 && r % 2 == 1) SEAT.add(N);
        for(int i = 0 ; i < M ; i ++ ) SEAT.add(seat[i]);
        Collections.sort(SEAT);
        for(int i = 0 ; i < SEAT.size() - 1 ; i ++ )
        {
            long nw = SEAT.get(i) , nx = SEAT.get(i + 1);
            long seg = nx - nw - 1 ;
            if(seg > 1 && seg % 2 == 1) Q.add(new Tuple(nw, nx, seg));
        }
        long ans = (long) N - SEAT.size() - Q.size();
        out.print(ans);
    }      
    public static void main(String[] args) 
    {
        new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start(); 
    }

    public void run() 
    {   
        solve();
        out.flush();
    }

    record ip(int fi , int se) { public String toString() { return fi +" "+ se ;} }
    record lp(long fi , long se) { public String toString() { return fi +" "+ se ;} }
    int max(int ... a) { int max = -1 ; for(int p : a) max = Math.max(max , p); return max; }
    int min(int ... a) { int min = Integer.MAX_VALUE ; for(int p : a) min = Math.min(min , p); return min; }
    long max(long ... a) { long max = -1 ; for(long p : a) max = Math.max(max , p); return max; }
    long min(long ... a) { long min = Long.MAX_VALUE ; for(long p : a) min = Math.min(min , p); return min; }
    int sum(int ... a) { int sum = 0 ; for(int p : a) sum += p ; return sum ;}
    long sum(long ... a) { long sum = 0 ; for(long p : a) sum += p ; return sum ;}
    int abs(int a , int b) { return (int) Math.abs(a - b) ; }
    long abs(long a , long b) { return (long) Math.abs(a - b) ; }
    int pow(int a , int b) { return (int) Math.pow(a , b) ; }
    long pow(long a , long b) { return (long) Math.pow(a , b) ; }
    long rec(long a) { return a == 1 ? 1 : a * rec(a - 1); }
    long [] recmod(int a , long MOD) { long [] recMod = new long[1 << 17] ; recMod[1] = 1 ; for(int i = 2 ; i < (1 << 17) ; i ++ ) recMod[i] = (recMod[i - 1] * i) % MOD9; return recMod; }
    int [] rev(int [] a) { int [] r = new int[a.length] ; int idx = a.length ; for(int p : a) r[--idx] = p ; return r ; }
    long [] rev(long [] a) { long [] r = new long[a.length] ; int idx = a.length ; for(long p : a) r[--idx] = p ; return r ; }
    int gcd(int a, int b) { return b == 0 ? a: gcd(b, a % b); }
    int lcm(int a, int b) { return a / gcd(a, b) * b; }
    long gcd(long a, long b) { return b == 0 ? a: gcd(b, a % b); }
    long lcm(long a, long b) { return a / gcd(a, b) * b; }
    int gcd(int ... a) { int gcd = 0 ; for(int p : a) gcd = gcd(gcd , p) ; return gcd ; }
    long gcd(long ... a) { long gcd = 0L ; for(long p : a) gcd = gcd(gcd , p) ; return gcd ; }
    int lcm(int ... a) { int lcm = 1 ; for(int p : a) lcm = lcm(lcm , p) ; return lcm ; }
    long lcm(long ... a) { long lcm = 1 ; for(long p : a) lcm = lcm(lcm , p) ; return lcm ; }
    char upper(char c) { return (char)('A' + (c - 'a')); }
    char lower(char c) { return (char)('a' + (c - 'A')); }
    double dist(lp p1 , lp p2) { return Math.sqrt((p1.fi - p2.fi) * (p1.fi - p2.fi) + (p1.se - p2.se) * (p1.se - p2.se)); }
    String yn(boolean a) { return a ? yes : no ; }
    String rev(String a) { return new StringBuilder(a).reverse().toString(); }
    void fill(int [] a , int v) { Arrays.fill(a , v); }
    void fill(long [] a , long v) { Arrays.fill(a , v); }
    void fill(int [][] a , int v) { for(int [] aa : a) fill(aa , v) ; }
    void fill(long [][] a , long v) { for(long [] aa : a) fill(aa , v) ; }
    void fill(int [][][] a , int v) { for(int [][] aa : a) fill(aa , v); }
    void fill(long [][][] a , long v) { for(long [][] aa : a) fill(aa , v); }
    int [] copy(int [] a) { return Arrays.copyOf(a , a.length); } 
    long [] copy(long [] a) { return Arrays.copyOf(a , a.length); } 
    String bin(int a , int len) { String b = Integer.toBinaryString(a); while(b.length() < len) b = "0" + b ; return b ; }
    public void debug(int [] a) { out.println(Arrays.toString(a)); fl();}
    public void debug(long [] a) { out.println(Arrays.toString(a)); fl();}
    public void debug(double [] a) { out.println(Arrays.toString(a)); fl();}
    public void debug(String [] a) { out.println(Arrays.toString(a)); fl();}
    public void debug(char [] a) { out.println(Arrays.toString(a)); fl();}
    public void debug(boolean [] a) { char [] c = conv(a); debug(c); fl();}
    public void debug(int [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
    public void debug(long [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
    public void debug(double [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
    public void debug(String [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
    public void debug(char [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
    public void debug(boolean [][] a) { char [][] c = new char [a.length][a[0].length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = conv(a[i]) ; debug(c); fl();}
    private char [] conv(boolean [] a) { char [] c = new char[a.length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = a[i] ? 'O' : 'X' ; return c ; }
    private void fl() { out.flush(); }

    PrintWriter out = new PrintWriter(System.out);
    In in = new In();
    boolean debug = true ;
    static final long MOD7 = 1000000007;
    static final long MOD9 = 998244353;
    static final int  inf = (1  << 30);
    static final long lnf = (1L << 60);
    final String yes = "Yes";
    final String no  = "No" ;
    final char [] dir = {'U','R','D','L'};
    final int [] dy4 = {-1,0,1,0};
    final int [] dx4 = {0,1,0,-1};
    final int [] dy8 = {-1,-1,-1,0,1,1,1,0};
    final int [] dx8 = {-1,0,1,1,1,0,-1,-1};

}

class UnionFind {

    private int[] rank;
    public int [] parent;
    private int [] size;
    private int n;

    UnionFind(int n) {
        this.parent = new int[n];
        this.rank = new int[n];
        this.size = new int[n];
        this.n = n ;
        for (int i = 0 ; i < n; i ++ ) {
            parent[i] = i;
            rank[i] = 0;
            size[i] = 1;
        }
    }
    List<List<Integer>> getDSU() {
        List<List<Integer>> Group = new ArrayList<>();
        Map<Integer,List<Integer>> mp = new HashMap<>();
        for(int i = 0 ; i < n ; i ++ ) {
            int par = find(i);
            if(!mp.containsKey(par)) {
                mp.put(par , new ArrayList<>());
            }
            mp.get(par).add(i);
        }
        for(List<Integer> lists : mp.values()) {
            Group.add(new ArrayList<>(lists));
        }
        return Group;
    }
    int size(int x){
        return size[find(x)];
    }

    int find(int x) {
        if (x == parent[x]) {
            return x;
        } else {
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    boolean same(int x, int y) {
        return find(x) == find(y);
    }

    void unite(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);

        if (xRoot == yRoot) {
            return;
        }
        if (rank[xRoot] > rank[yRoot]) {
            parent[yRoot] = xRoot;
        } else if (rank[xRoot] < rank[yRoot]) {
            parent[xRoot] = yRoot;
        } else {
            parent[xRoot] = yRoot;
            rank[xRoot]++;
            size[yRoot] += size[xRoot];
        }
    }
}

class mint {

    private long value;
    private final long MOD;

    mint(long value, long MOD) 
    {
        this.MOD = MOD;
        this.value = (value % MOD + MOD) % MOD;
    }

    public mint add(mint other) 
    {
        return new mint((this.value + other.value) % MOD, MOD);
    }

    public mint subtract(mint other) 
    {
        return new mint((this.value - other.value + MOD) % MOD, MOD);
    }

    public mint multiply(mint other) 
    {
        return new mint((this.value * other.value) % MOD, MOD);
    }

    public mint inverse() 
    {
        return new mint(pow(this.value, MOD - 2), MOD);
    }

    public mint divide(mint other) 
    {
        return this.multiply(other.inverse());
    }

    private long pow(long a, long b) 
    {
        long res = 1;
        while (b > 0) 
        {
            if ((b & 1) != 0) res = (res * a) % MOD;
            a = (a * a) % MOD;
            b >>= 1;
        }
        return res;
    }

    public long getVal() 
    {
        return value;
    }

    @Override
    public String toString() 
    {
        return String.valueOf(value);
    }
}

class In
{

    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;
    }

    private  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());
    }

    public char nextChar() {
        return next().charAt(0);
    }
    
    public int [] IntArray(int n) {
        final int [] Array = new int [n];
        for(int i = 0 ; i < n ; i ++ ) {
            Array[i] = nextInt();
        }
        return Array;
    }
    public int [][] IntArray(int n , int m) {
        final int [][] Array = new int [n][m];
        for(int i = 0 ; i < n ; i ++ ) {
            Array[i] = IntArray(m);
        }
        return Array;
    }   
    public long [] LongArray(int n) {
        final long [] Array = new long [n];
        for(int i = 0 ; i < n ; i ++ ) {
            Array[i] = nextLong();
        }
        return Array;
    }
    public long [][] LongArray(int n , int m) {
        final long [][] Array = new long [n][m];
        for(int i = 0 ; i < n ; i ++ ) {
            Array[i] = LongArray(m);
        }
        return Array;
    }
    public String [] StringArray(int n) {
        final String [] Array = new String [n];
        for(int i = 0 ; i < n ; i ++ ) {
            Array[i] = next();
        }
        return Array;
    }
    public char [] CharArray(int n) {
        final char [] Array = new char[n];
        for(int i = 0 ; i < n ; i ++ ) {
            Array[i] = next().charAt(0);
        }
        return Array;
    }
    public char [][] CharArray(int n , int m) {
        final char [][] Array = new char [n][m];
        for(int i = 0 ; i < n ; i ++ ) {
            Array[i] = next().toCharArray();
        }
        return Array;
    }
    public char [][] CharArray2(int n , int m) {
        final char [][] Array = new char [n][m];
        for(int i = 0 ; i < n ; i ++ ) {
            for(int j = 0 ; j < m ; j ++ ) {
                Array[i][j] = next().charAt(0);
            }
        }
        return Array;
    }
    public List<Integer> [] Graph(int n) {
        @SuppressWarnings("unchecked")
        List<Integer> [] G = new ArrayList[n];
        for(int i = 0 ; i < n ; i ++ ) {
            G[i] = new ArrayList<>();
        }
        return G ;
    }
}
yukicoder

結果

テストケース

ソースコード
