Submission #1359460

#TimeUsernameProblemLanguageResultExecution timeMemory
1359460faricaBOI Acronym (BOI25_boi)C++20
12 / 100
54 ms16100 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;

void solve() {
    int n;
    cin >> n;
    int grid[n+1][n+1];
    for(int i=1; i<=n; ++i) for(int j=i; j<=n; ++j) cin >> grid[i][j];
    int cnt = grid[1][n], l = 1, r = n;
    while(l+1<=n && grid[l+1][n] == cnt) ++l;
    while(r-1>=l && grid[l][r-1] == cnt) --r;
    vi ind;
    int B = 1, i = l;
    while(i+1<=n && grid[i][i+1]==2) {
        ind.push_back(i);
        ++i, ++B;
    }
    ind.push_back(i);
    ++i;
    for(; i<=r; ++i) {
        if(ind.back() == i-1) {
            while(i+1<=n && grid[i][i+1]==2) ++i;
            continue;
        }
        int j = i;
        while(j+1<=n && grid[j][j+1]==2) ++j;
        int len = j-i+1;
        bool cur = 0;
        if(len > n-cnt) cur = 1;
        else if(2*(B+len) > (j-l+1)) { // mozemo sigurno znati je li B
            if(grid[l][j] == B+len) cur = 1;
        } else {
            if(grid[j+1][r] != cnt - B) cur = 1;
        }
        if(cur) {
            for(int k=i; k<=j; ++k) ind.push_back(k);
            B += len;
        }
        i = j;
    }
    for(int x: ind) cout << x << " ";
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    while(tc--) solve();

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...