QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113865#6636. Longest Strictly Increasing SequenceITMO_pengzoo#AC ✓2ms3524kbC++201.5kb2023-06-19 21:01:502023-06-19 21:01:53

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-19 21:01:53]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3524kb
  • [2023-06-19 21:01:50]
  • 提交

answer

//  Nikita Golikov, 2023

#include <bits/stdc++.h>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#ifdef GOLIKOV
  #include "/Users/golikovnik/contests/debug.h"
#else
  #define debug(...) ;
#endif

template <class A, class B>
bool smin(A& x, B&& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}

template <class A, class B>
bool smax(A& x, B&& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

void solveTest() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto& x : a) {
    cin >> x;
  }
  int level = 0;
  vector<int> ans;
  for (int i = 0; i < n; ++i) {
    int j = i;
    while (j < n && a[i] == a[j]) {
      ++j;
    }
    if (a[i] != level + 1) {
      cout << "NO\n";
      return;
    }
    for (int t = j - 1; t >= i; --t) {
      ans.push_back(t + 1);
    }
    level++;
    i = j - 1;
  }
  cout << "YES\n";
  for (int x : ans) {
    cout << x << ' ';
  }
  cout << '\n';
}

int main() {
#ifdef GOLIKOV
  assert(freopen("in", "rt", stdin));
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int tests_;
  cin >> tests_;
  for (int tt_ = 1; tt_ <= tests_; ++tt_) {
    solveTest();
  }

#ifdef GOLIKOV
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
      chrono::high_resolution_clock::now()
          - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3512kb

input:

2
6
1 2 3 2 5 7
2
1 2

output:

NO
YES
1 2 

result:

ok t=2 (2 test cases)

Test #2:

score: 0
Accepted
time: 2ms
memory: 3524kb

input:

3483
5
2 3 5 1 1
2
8 1
10
1 2 3 4 4 5 6 6 6 7
10
1 1 2 2 2 2 3 4 4 5
2
5 8
3
7 10 8
5
4 1 3 3 8
10
1 2 2 2 2 2 2 3 3 3
10
1 1 2 3 4 5 5 5 5 6
9
1 2 3 4 5 5 6 6 7
7
8 8 8 8 9 1 2
5
8 9 8 3 5
10
1 2 3 3 3 3 4 4 4 5
5
7 1 6 4 3
7
5 6 8 6 1 5 5
10
1 2 2 3 4 4 4 4 5 5
3
10 4 5
3
1 5 3
5
2 8 1 2 1
3
7 8 3...

output:

NO
NO
YES
1 2 3 5 4 6 9 8 7 10 
YES
2 1 6 5 4 3 7 9 8 10 
NO
NO
NO
YES
1 7 6 5 4 3 2 10 9 8 
YES
2 1 3 4 5 9 8 7 6 10 
YES
1 2 3 4 6 5 8 7 9 
NO
NO
YES
1 2 6 5 4 3 9 8 7 10 
NO
NO
YES
1 3 2 4 8 7 6 5 10 9 
NO
NO
NO
NO
NO
NO
YES
3 2 1 5 4 7 6 9 8 
NO
NO
NO
NO
NO
NO
NO
YES
1 2 5 4 3 8 7 6 10 9 
YES
2 ...

result:

ok t=3483 (3483 test cases)