oj.uz

Submission #257301

# Submission time Handle Problem Language Result Execution time Memory
257301 2020-08-04T05:17:08 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;
}

int calc(int p1, int p2) {
  int ret = 0;

  for (int a = 1; a <= n; ++a) {
    for (int b = 1; b <= n; ++b) {
      for (int x = 0; x < 2; ++x) {
        for (int y = 0; y < 2; ++y) {
          dp[x][y] = 0;
        }
      }
      
      dp[bit(arr[a], p1)][bit(arr[b], p2)] = 1;
      
      for (int i = 1; i <= q; ++i) {
        auto &[l, r, k] = que[i];
        
        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 <= a && a <= r) {
              nx ^= bit(k, p1);
            }
            
            if (l <= b && b <= r) {
              ny ^= bit(k, p2);
            }
            
            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;
          }
        }
      }
      
      ret = addMod(ret, mulMod(dp[1][1], mulMod(min(a, b), n - max(a, b) + 1)));
    }
  }
  
  return ret;
}

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 a = 0; a < 7; ++a) {
    for (int b = 0; b < 7; ++b) {
      ans = addMod(ans, mulMod(calc(a, b), (1 << (a + b))));
    }
  }
  
  printf("%d\n", ans);
}

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

  return 0;
}

Compilation message

xorsum.cpp: In function 'void solve()':
xorsum.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
xorsum.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~
xorsum.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
xorsum.cpp:102: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 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 115 ms 376 KB Output is correct
7 Correct 91 ms 256 KB Output is correct
8 Correct 121 ms 376 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 256 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 2072 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 23 ms 256 KB Output is correct
2 Correct 22 ms 256 KB Output is correct
3 Correct 22 ms 256 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 256 KB Output is correct
2 Correct 22 ms 256 KB Output is correct
3 Correct 22 ms 256 KB Output is correct
4 Execution timed out 1 ms 256 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 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 115 ms 376 KB Output is correct
7 Correct 91 ms 256 KB Output is correct
8 Correct 121 ms 376 KB Output is correct
9 Correct 23 ms 256 KB Output is correct
10 Correct 22 ms 256 KB Output is correct
11 Correct 22 ms 256 KB Output is correct
12 Execution timed out 2093 ms 256 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 115 ms 376 KB Output is correct
7 Correct 91 ms 256 KB Output is correct
8 Correct 121 ms 376 KB Output is correct
9 Correct 23 ms 256 KB Output is correct
10 Correct 22 ms 256 KB Output is correct
11 Correct 22 ms 256 KB Output is correct
12 Execution timed out 1 ms 256 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 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 115 ms 376 KB Output is correct
7 Correct 91 ms 256 KB Output is correct
8 Correct 121 ms 376 KB Output is correct
9 Execution timed out 1 ms 256 KB Time limit exceeded (wall clock)
10 Halted 0 ms 0 KB -