結果
| 問題 |
No.2486 Don't come next to me
|
| ユーザー |
 Asahi
|
| 提出日時 | 2023-09-29 23:13:49 |
| 言語 | Java (openjdk 23) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | WA * 20 |
ソースコード
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 ;
}
}