提出 #828040

ソースコード 拡げる

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;


int main() {
    long n, l;
    cin >> n >> l;
    vector<long> a (n);
    long lastKnot = 1000000;
    
    // Optimization 2: no need for further input if endpoint found already
    for (long i = 0; i < n; i++) {
        cin >> a[i];
        if (i > 0) if (a[i] + a[i-1] >= l) {
            lastKnot = i;
            break;
        }
    }
    
    // Can be approached from behind: can a rope be fully tied from fully untied state?
    // Let's try completely optimizing it: if one 1st tie is possible, then you can tie it fully 
    // from that position without checking anything anymore, because it will always be > l
    
    
    if (lastKnot != 1000000) {
        ostringstream ss;
        for (int i = 1; i < lastKnot; i++) ss << i << endl;
        for (int i = n-1; i >= lastKnot; i--) ss << i << endl;
        cout << "Possible" << endl << ss.str();
    } else {
        cout << "Impossible";
    }
}

提出情報

提出日時
問題 C - Knot Puzzle
ユーザ tom_mol
言語 C++14 (GCC 5.4.1)
得点 500
コード長 1085 Byte
結果 AC
実行時間 81 ms
メモリ 2820 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 3
AC × 35
セット名 テストケース
Sample 0_00.txt, 0_01.txt, 0_02.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt
ケース名 結果 実行時間 メモリ
0_00.txt AC 4 ms 256 KiB
0_01.txt AC 4 ms 256 KiB
0_02.txt AC 4 ms 256 KiB
1_00.txt AC 4 ms 256 KiB
1_01.txt AC 4 ms 256 KiB
1_02.txt AC 19 ms 2820 KiB
1_03.txt AC 32 ms 1024 KiB
1_04.txt AC 19 ms 2820 KiB
1_05.txt AC 32 ms 1024 KiB
1_06.txt AC 46 ms 2820 KiB
1_07.txt AC 32 ms 1024 KiB
1_08.txt AC 19 ms 2820 KiB
1_09.txt AC 32 ms 1024 KiB
1_10.txt AC 33 ms 2820 KiB
1_11.txt AC 33 ms 1024 KiB
1_12.txt AC 19 ms 2820 KiB
1_13.txt AC 75 ms 1024 KiB
1_14.txt AC 19 ms 2820 KiB
1_15.txt AC 4 ms 256 KiB
1_16.txt AC 4 ms 256 KiB
1_17.txt AC 81 ms 1024 KiB
1_18.txt AC 26 ms 2820 KiB
1_19.txt AC 75 ms 1024 KiB
1_20.txt AC 69 ms 896 KiB
1_21.txt AC 64 ms 2820 KiB
1_22.txt AC 76 ms 2820 KiB
1_23.txt AC 71 ms 1024 KiB
1_24.txt AC 40 ms 2692 KiB
1_25.txt AC 72 ms 1024 KiB
1_26.txt AC 61 ms 2692 KiB
1_27.txt AC 19 ms 2820 KiB
1_28.txt AC 19 ms 2820 KiB
1_29.txt AC 18 ms 2692 KiB
1_30.txt AC 19 ms 2820 KiB
1_31.txt AC 18 ms 2692 KiB