oj.uz

Submission #1029169

# Submission time Handle Problem Language Result Execution time Memory
1029169 2024-07-20T13:25:21 Z 42kangaroo Digital Circuit (IOI22_circuit) C++17
16 / 100
 821 ms 5052 KB 
#include "circuit.h"

#include <vector>

using namespace std;

int ma;
using ll = long long;

constexpr ll mod = 1000002022;

struct SVal {
	ll pos, fpos, tPos;
};

SVal comb(SVal l, SVal r) {
	return SVal{
			((l.tPos * r.tPos) % mod - ((l.tPos - l.pos) * (r.tPos - r.pos)) % mod + mod + (l.pos * r.pos) % mod) % mod,
			((l.tPos * r.tPos) % mod - ((l.tPos - l.fpos) * (r.tPos - r.fpos)) % mod + mod + (l.fpos * r.fpos) % mod) % mod, (2 * l.tPos * r.tPos) % mod};
}

struct SegTe {
	vector<SVal> a;
	vector<bool> lazy;

	void push(int i) {
		if (lazy[i]) {
			swap(a[i].pos, a[i].fpos);
			if (2 * i + 2 < a.size()) {
				lazy[2 * i + 1] = !lazy[2 * i + 1];
				lazy[2 * i + 2] = !lazy[2 * i + 2];
			}
			lazy[i] = false;
		}
	}

	SVal toggle(int l, int r, int i, int lq, int rq) {
		push(i);
		if (rq <= l || r <= lq) return a[i];
		if (lq <= l && r <= rq) {
			lazy[i] = true;
			push(i);
			return a[i];
		}
		int m = (l + r) / 2;
		return a[i] = comb(toggle(l, m, 2 * i + 1, lq, rq), toggle(m, r, 2 * i + 2, lq, rq));
	}
};

SegTe se;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	ma = N;
	se = SegTe{vector<SVal>(2 * M, SVal{0, 1, 1}), vector<bool>(2 * M, false)};
	for (int i = 0; i < M; ++i) {
		se.toggle(0, M, 0, i, i + 1);
		if (A[i] == 0) {
			se.toggle(0, M, 0, i, i + 1);
		}
	}
}

int count_ways(int L, int R) {
	L -= ma;
	R -= ma;
	return se.toggle(0, ma + 1, 0, L, R + 1).pos;
}

Compilation message

circuit.cpp: In member function 'void SegTe::push(int)':
circuit.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<SVal>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |    if (2 * i + 2 < a.size()) {
      |        ~~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Runtime error 1 ms 600 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 2736 KB Output is correct
2 Correct 681 ms 5052 KB Output is correct
3 Correct 710 ms 5040 KB Output is correct
4 Correct 678 ms 4952 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 2736 KB Output is correct
2 Correct 681 ms 5052 KB Output is correct
3 Correct 710 ms 5040 KB Output is correct
4 Correct 678 ms 4952 KB Output is correct
5 Correct 613 ms 2756 KB Output is correct
6 Correct 821 ms 5052 KB Output is correct
7 Correct 789 ms 4952 KB Output is correct
8 Correct 728 ms 4952 KB Output is correct
9 Correct 310 ms 344 KB Output is correct
10 Correct 653 ms 600 KB Output is correct
11 Correct 639 ms 600 KB Output is correct
12 Correct 575 ms 600 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Runtime error 1 ms 600 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -