oj.uz

Submission #257297

# Submission time Handle Problem Language Result Execution time Memory
257297 2020-08-04T05:11:20 Z BThero Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 384 KB 
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)1e3 + 5;
const int MOD = (int)1e9 + 7;

array<int, 3> que[MAXN];
int dp[2][2], ndp[2][2];
int arr[MAXN];
int n, q, ans;

int addMod(int a, int b, int m = MOD) {
  a += b;
  
  if (m <= a) {
    a -= m;
  }
  
  return a;
}

int mulMod(int a, int b, int m = MOD) {
  return a * 1ll * b % m;
}

int bit(int x, int p) {
  return (x >> p) & 1;
}

void solve() {
  scanf("%d", &n);
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
  }
  
  scanf("%d", &q);
  
  for (int i = 1; i <= q; ++i) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    que[i] = {l, r, x};
  }
  
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      int cur = 0;
    
      for (int b1 = 0; b1 < 7; ++b1) {
        for (int b2 = 0; b2 < 7; ++b2) {
          for (int x = 0; x < 2; ++x) {
            for (int y = 0; y < 2; ++y) {
              dp[x][y] = ndp[x][y] = 0;
            }
          }
          
          dp[bit(arr[i], b1)][bit(arr[j], b2)] = 1;
          
          for (int k = 1; k <= q; ++k) {
            auto &[l, r, t] = que[k];
            
            for (int x = 0; x < 2; ++x) {
              for (int y = 0; y < 2; ++y) {
                ndp[x][y] = addMod(ndp[x][y], dp[x][y]);
                int nx = x, ny = y;
                
                if (l <= i && i <= r) {
                  nx ^= bit(t, b1);
                }
                
                if (l <= j && j <= r) {
                  ny ^= bit(t, b2);
                }
                
                ndp[nx][ny] = addMod(ndp[nx][ny], dp[x][y]);
              }
            }
            
            for (int x = 0; x < 2; ++x) {
              for (int y = 0; y < 2; ++y) {
                dp[x][y] = ndp[x][y];
                ndp[x][y] = 0;
              }
            }
          }
          
          cur = addMod(cur, mulMod(dp[1][1], (1 << (b1 + b2))));
        }
      }
      
      ans = addMod(ans, mulMod(cur, mulMod(min(i, j), n - max(i, j) + 1)));
    }
  }
  
  printf("%d\n", ans);
}

int main() {
  int tt = 1;
  
  while (tt--) {
    solve();
  }

  return 0;
}

Compilation message

xorsum.cpp: In function 'void solve()':
xorsum.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
xorsum.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~
xorsum.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
xorsum.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &l, &r, &x);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 109 ms 368 KB Output is correct
7 Correct 86 ms 256 KB Output is correct
8 Correct 114 ms 376 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 384 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2084 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 376 KB Output is correct
2 Correct 23 ms 256 KB Output is correct
3 Correct 20 ms 384 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 376 KB Output is correct
2 Correct 23 ms 256 KB Output is correct
3 Correct 20 ms 384 KB Output is correct
4 Execution timed out 1 ms 384 KB Time limit exceeded (wall clock)
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 109 ms 368 KB Output is correct
7 Correct 86 ms 256 KB Output is correct
8 Correct 114 ms 376 KB Output is correct
9 Correct 20 ms 376 KB Output is correct
10 Correct 23 ms 256 KB Output is correct
11 Correct 20 ms 384 KB Output is correct
12 Execution timed out 2086 ms 384 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 109 ms 368 KB Output is correct
7 Correct 86 ms 256 KB Output is correct
8 Correct 114 ms 376 KB Output is correct
9 Correct 20 ms 376 KB Output is correct
10 Correct 23 ms 256 KB Output is correct
11 Correct 20 ms 384 KB Output is correct
12 Execution timed out 1 ms 384 KB Time limit exceeded (wall clock)
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 109 ms 368 KB Output is correct
7 Correct 86 ms 256 KB Output is correct
8 Correct 114 ms 376 KB Output is correct
9 Execution timed out 1 ms 384 KB Time limit exceeded (wall clock)
10 Halted 0 ms 0 KB -