Submission #2839764


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> Pair;
vector<long long> A;

int main(){
    long long i, j, k;
    long long N;
    cin >> N;
    A.resize(N);
    for(i=0; i<N; i++) cin >> A[i];
    vector<long long> order(N);
    for(i=0; i<N; i++) order[i] = i;
    sort(order.begin(), order.end(),
        [](long long i, long long j){return A[i] < A[j];}
    );
    vector<long long> diff(N);
    for(i=1; i<N; i++) diff[i] = A[order[i]] - A[order[i-1]];
    vector<Pair> ans;
    ans.push_back(make_pair(order[0], -1));
    for(j=0; j<=29; j++){
        for(i=1; i<N; i++){
            if(diff[i] & (1<<j)){
                ans.push_back(make_pair(order[i], order[0]));
            }
        }
        if(j == 29){
            ans.push_back(make_pair(order[0], -1));
        }else{
            ans.push_back(make_pair(order[0], order[0]));
        }
    }
    for(i=1; i<N; i++){
        if(A[order[i]] == 1){
            ans.push_back(make_pair(order[i], -1));
        }else{
            ans.push_back(make_pair(order[i], order[i-1]));
        }
    }
    vector<long long> test(N);
    //for(i=0; i<N; i++) test[i] = 0;

    cout << ans.size() << endl;
    for(i=0; i<ans.size(); i++){
        if(ans[i].second == -1){
            cout << 1 << " " << ans[i].first+1 << endl;
            //test[ans[i].first] = 1;
        }else{
            cout << 2 << " " << ans[i].first+1 << " " << ans[i].second+1 << endl;
            //test[ans[i].first] += test[ans[i].second];
        }
    }
    /*
    for(i=0; i<N; i++){
        if(A[i] != test[i]){
            cout << "error" << endl;
            return 1;
        }
    }*/
    return 0;
}

Submission Info

Submission Time
Task H - 新入生歓迎数列 - Hard
User betrue12
Language C++14 (GCC 5.4.1)
Score 510
Code Size 1735 Byte
Status
Exec Time 2651 ms
Memory 46816 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
Subtask1 60 / 60 subtask1_in01.txt, subtask1_in02.txt, subtask1_in03.txt, subtask1_in04.txt, subtask1_in05.txt
Subtask2 140 / 140 subtask1_in01.txt, subtask1_in02.txt, subtask1_in03.txt, subtask1_in04.txt, subtask1_in05.txt, subtask2_in01.txt, subtask2_in02.txt, subtask2_in03.txt
Subtask3 80 / 80 subtask1_in01.txt, subtask1_in02.txt, subtask1_in03.txt, subtask1_in04.txt, subtask1_in05.txt, subtask2_in01.txt, subtask2_in02.txt, subtask2_in03.txt, subtask3_in01.txt, subtask3_in02.txt, subtask3_in03.txt, subtask3_in04.txt
Subtask4 230 / 230 subtask1_in01.txt, subtask1_in02.txt, subtask1_in03.txt, subtask1_in04.txt, subtask1_in05.txt, subtask2_in01.txt, subtask2_in02.txt, subtask2_in03.txt, subtask3_in01.txt, subtask3_in02.txt, subtask3_in03.txt, subtask3_in04.txt, subtask4_in01.txt, subtask4_in02.txt, subtask4_in03.txt, subtask4_in04.txt, subtask4_in05.txt, subtask4_in06.txt
Subtask5 0 / 270 subtask1_in01.txt, subtask1_in02.txt, subtask1_in03.txt, subtask1_in04.txt, subtask1_in05.txt, subtask2_in01.txt, subtask2_in02.txt, subtask2_in03.txt, subtask3_in01.txt, subtask3_in02.txt, subtask3_in03.txt, subtask3_in04.txt, subtask4_in01.txt, subtask4_in02.txt, subtask4_in03.txt, subtask4_in04.txt, subtask4_in05.txt, subtask4_in06.txt, subtask5_in01.txt, subtask5_in02.txt, subtask5_in03.txt, subtask5_in04.txt
Subtask6 0 / 220 subtask1_in01.txt, subtask1_in02.txt, subtask1_in03.txt, subtask1_in04.txt, subtask1_in05.txt, subtask2_in01.txt, subtask2_in02.txt, subtask2_in03.txt, subtask3_in01.txt, subtask3_in02.txt, subtask3_in03.txt, subtask3_in04.txt, subtask4_in01.txt, subtask4_in02.txt, subtask4_in03.txt, subtask4_in04.txt, subtask4_in05.txt, subtask4_in06.txt, subtask5_in01.txt, subtask5_in02.txt, subtask5_in03.txt, subtask5_in04.txt, subtask6_in01.txt, subtask6_in02.txt, subtask6_in03.txt, subtask6_in04.txt, subtask6_in05.txt, subtask6_in06.txt, subtask6_in07.txt, subtask6_in08.txt, subtask6_in09.txt, subtask6_in10.txt, subtask6_in11.txt, subtask6_in12.txt, subtask6_in13.txt, subtask6_in14.txt, subtask6_in15.txt
Case Name Status Exec Time Memory
subtask1_in01.txt 1 ms 256 KB
subtask1_in02.txt 1 ms 256 KB
subtask1_in03.txt 1 ms 256 KB
subtask1_in04.txt 1 ms 256 KB
subtask1_in05.txt 1 ms 256 KB
subtask2_in01.txt 139 ms 2548 KB
subtask2_in02.txt 138 ms 2548 KB
subtask2_in03.txt 147 ms 2548 KB
subtask3_in01.txt 264 ms 6000 KB
subtask3_in02.txt 260 ms 5232 KB
subtask3_in03.txt 261 ms 6128 KB
subtask3_in04.txt 37 ms 1148 KB
subtask4_in01.txt 392 ms 6636 KB
subtask4_in02.txt 392 ms 6636 KB
subtask4_in03.txt 396 ms 7148 KB
subtask4_in04.txt 399 ms 6636 KB
subtask4_in05.txt 93 ms 2292 KB
subtask4_in06.txt 56 ms 1784 KB
subtask5_in01.txt 2130 ms 38884 KB
subtask5_in02.txt 2162 ms 38624 KB
subtask5_in03.txt 2134 ms 37092 KB
subtask5_in04.txt 2122 ms 37476 KB
subtask6_in01.txt 2637 ms 46688 KB
subtask6_in02.txt 2639 ms 45664 KB
subtask6_in03.txt 2651 ms 46432 KB
subtask6_in04.txt 2631 ms 46816 KB
subtask6_in05.txt 445 ms 12524 KB
subtask6_in06.txt 1570 ms 28900 KB
subtask6_in07.txt 460 ms 12524 KB
subtask6_in08.txt 439 ms 12524 KB
subtask6_in09.txt 771 ms 17896 KB
subtask6_in10.txt 791 ms 19176 KB
subtask6_in11.txt 773 ms 17640 KB
subtask6_in12.txt 671 ms 16104 KB
subtask6_in13.txt 553 ms 15464 KB
subtask6_in14.txt 500 ms 13420 KB
subtask6_in15.txt 469 ms 12908 KB