結果

問題 No.831 都市めぐり
ユーザー Grenache
提出日時 2019-05-24 22:49:32
言語 Java
(openjdk 23)
結果
AC  
実行時間 644 ms / 2,000 ms
コード長 1,660 bytes
コンパイル時間 3,696 ms
コンパイル使用メモリ 79,996 KB
実行使用メモリ 159,976 KB
最終ジャッジ日時 2024-09-17 11:09:50
合計ジャッジ時間 9,982 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.*;
import java.util.*;
public class Main_yukicoder831_1 {
    private static Scanner sc;
    private static Printer pr;
    private static void solve() {
        int n = sc.nextInt();
        
        if (n == 1) {
            pr.println(0);
            return;
        }
        
        Deque<Integer> q = new ArrayDeque<>(n);
        for (int i = 1; i < n; i++) {
            q.add(i);
        }
        
        Deque<Integer> ans = new ArrayDeque<>(n);
        ans.add(0);
        while (!q.isEmpty()) {
            int last = ans.getLast();
            int first = ans.getFirst();
            int large = q.getLast();
            int small = q.getFirst();
            
            int diff1 = Math.abs(large - last);
            int diff2 = Math.abs(large - first);
            int diff3 = Math.abs(small - last);
            int diff4 = Math.abs(small - first);
            if (diff1 >= diff2 && diff1 >= diff3 && diff1 >= diff4) {
                ans.addLast(large);
                q.removeLast();
            } else if (diff2 >= diff1 && diff2 >= diff3 && diff2 >= diff4) {
                ans.addFirst(large);
                q.removeLast();
            } else if (diff3 >= diff1 && diff3 >= diff2 && diff3 >= diff4) {
                ans.addLast(small);
                q.removeFirst();
            } else {
                ans.addFirst(small);
                q.removeFirst();
            }
        }
        
        List<Integer> list = new ArrayList<>(ans);
        long cost = 0;
        for (int i = 0; i < n; i++) {
            int ii = list.get(i) + 1;
            int jj = list.get((i + 1) % n) + 1;
            cost += (long)ii * jj + jj - ii;
        }
//      pr.println(list);
        pr.println(cost);
    }
    // ---------------------------------------------------
    public static void main(String[] args) {
        sc = new Scanner(System.in);
        pr = new Printer(System.out);
            
        solve();
            
        pr.close();
        sc.close();
    }
    static class Printer extends PrintWriter {
        Printer(OutputStream out) {
            super(out);
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0