Submission #467163

#	Time	Username	Problem	Language	Result	Execution time	Memory
467163		radaiosm7	Exam (eJOI20_exam)	C++98	12 / 100	30 ms	2324 KiB

exam

#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]) {
        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 (stderr)

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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22