oj.uz

Submission #467166

# Submission time Handle Problem Language Result Execution time Memory
467166 2021-08-21T19:44:03 Z radaiosm7 Exam (eJOI20_exam) C++
12 / 100
 1000 ms 2372 KB 
#include <bits/stdc++.h>
using namespace std;
int n, i, j, l, r;
int a[100005];
int b[100005];
int c[100005];
int vis[100005];
int seg[400020];
bool lazy[400020];
int dp[5005];

void Update(int from, int to, int start=0, int ende=n-1, int indx=1) {
  if (lazy[indx]) return;
  if (from == start && to == ende) {
    seg[indx] = to-from+1;
    lazy[indx] = true;
    return;
  }

  int mid = (start+ende)/2;

  if (to <= mid) Update(from, to, start, mid, 2*indx);
  else if (from > mid) Update(from, to, mid+1, ende, 2*indx+1);
  else {
    Update(from, mid, start, mid, 2*indx);
    Update(mid+1, to, mid+1, ende, 2*indx+1);
  }
  seg[indx] = seg[2*indx]+seg[2*indx+1];
}

int rec(int indx) {
  if (indx == n) {
    int cc = 0;
    int ok = 1;

    for (int i=0; i < n; ++i) cc += (a[c[i]] == b[i]);

    for (int i=0; i < n; ++i) {
      if (c[i] < i) {
        for (int j=i; j > c[i]; --j) ok &= (a[j] <= a[c[i]]);
      }

      else if (c[i] > i) {
        for (int j=i; j < c[i]; ++j) ok &= (a[j] <= a[c[i]]);
      }
    }

    return cc*ok;
  }

  else {
    int curr = 0;
    for (int j=0; j < n; ++j) {
      if (vis[j] && c[indx-1]==j) {
        c[indx] = j;
        curr = max(curr, rec(indx+1));
      }

      else if (!vis[j]) {
        c[indx] = j;
        vis[j] = true;
        curr = max(curr, rec(indx+1));
        vis[j] = false;
      }
    }

    return curr;
  }
}

int main() {
  scanf("%d", &n);
  for (i=0; i < n; ++i) scanf("%d", &a[i]);
  for (i=0; i < n; ++i) scanf("%d", &b[i]);

  if (n <= 10) {
    printf("%d\n", rec(0));
  }

  else {
    for (i=0; i < n; ++i) {
      if (a[i] == b[0]) {
        for (l=i; l-1 >= 0 && a[l-1]<a[i]; --l);
        for (r=i; r+1 < n && a[r+1]<a[i]; ++r);
        Update(l, r);
      }
    }

    printf("%d\n", seg[1]);
  }

  return 0;
}

Compilation message

exam.cpp: In function 'int main()':
exam.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
exam.cpp:73:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   for (i=0; i < n; ++i) scanf("%d", &a[i]);
      |                         ~~~~~^~~~~~~~~~~~~
exam.cpp:74:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   for (i=0; i < n; ++i) scanf("%d", &b[i]);
      |                         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 8 ms 204 KB Output is correct
4 Execution timed out 1088 ms 204 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 716 KB Output is correct
3 Correct 20 ms 940 KB Output is correct
4 Correct 25 ms 1092 KB Output is correct
5 Correct 27 ms 1080 KB Output is correct
6 Correct 25 ms 2216 KB Output is correct
7 Correct 21 ms 2372 KB Output is correct
8 Correct 27 ms 1084 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 8 ms 204 KB Output is correct
4 Execution timed out 1088 ms 204 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 8 ms 204 KB Output is correct
4 Execution timed out 1088 ms 204 KB Time limit exceeded
5 Halted 0 ms 0 KB -