QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#582787 | #9170. Cycle Game | ucup-team4435# | WA | 0ms | 3752kb | C++20 | 8.2kb | 2024-09-22 17:27:12 | 2024-09-22 17:27:13 |
Judging History
answer
// Copyright (C) 2003-2024 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/** @file stdc++.h
* This is an implementation file for a precompiled header.
*/
// 17.4.1.2 Headers
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <csetjmp>
#include <cstdarg>
#include <cstddef>
#include <cstdlib>
#if __cplusplus >= 201103L
#include <cstdint>
#endif
// C++
#include <bitset>
#include <complex>
#include <algorithm>
#include <bitset>
#include <functional>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <numeric>
#include <typeinfo>
#include <utility>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <initializer_list>
#include <ratio>
#include <scoped_allocator>
#include <tuple>
#include <typeindex>
#include <type_traits>
#endif
#if __cplusplus >= 201402L
#endif
#if __cplusplus >= 201703L
#include <any>
// #include <execution>
#include <optional>
#include <variant>
#include <string_view>
#endif
#if __cplusplus >= 202002L
#include <bit>
#include <compare>
#include <concepts>
#include <numbers>
#include <ranges>
#include <span>
#include <source_location>
#include <version>
#endif
#if __cplusplus > 202002L
#include <expected>
#include <stdatomic.h>
#if __cpp_impl_coroutine
# include <coroutine>
#endif
#endif
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cuchar>
#endif
// C++
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#if __cplusplus >= 201402L
#include <shared_mutex>
#endif
#if __cplusplus >= 201703L
#include <any>
#include <charconv>
// #include <execution>
#include <filesystem>
#include <optional>
#include <memory_resource>
#include <variant>
#endif
#if __cplusplus >= 202002L
#include <barrier>
#include <bit>
#include <compare>
#include <concepts>
#include <format>
#include <latch>
#include <numbers>
#include <ranges>
#include <span>
#include <stop_token>
#include <semaphore>
#include <source_location>
#include <syncstream>
#include <version>
#endif
#if __cplusplus > 202002L
#include <expected>
#include <generator>
#include <print>
#include <spanstream>
#if __has_include(<stacktrace>)
# include <stacktrace>
#endif
#include <stdatomic.h>
#include <stdfloat>
#endif
#if __cplusplus > 202302L
#include <text_encoding>
#endif
namespace std {
template<typename T>
int __lg(T x) {
assert(x > 0);
int ans = 0;
while (x > 0) {
ans += 1;
x >>= 1;
}
return ans - 1;
}
}
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
vector<pair<int, int>> stk;
int n{};
int e = 0, t = 0;
DSU() = default;
DSU(int n) : n(n), p(n), sz(n, 1) {
iota(p.begin(), p.end(), 0);
stk.clear();
}
int leader(int a) {
return p[a] == a ? a : leader(p[a]);
}
bool unite(int a, int b) {
a = leader(a), b = leader(b);
if (a == b) {
return false;
}
t += 1;
if (sz[a] < sz[b]) {
swap(a, b);
}
sz[a] += sz[b];
p[b] = a;
stk.back() = {a, b};
return true;
}
bool same(int a, int b) {
return leader(a) == leader(b);
}
void undo() {
e -= 1;
assert(!stk.empty());
auto [a, b] = stk.back();
stk.pop_back();
if (a != -1) {
p[b] = b;
t -= 1;
sz[a] -= sz[b];
}
}
void update(pair<int, int> a) {
e += 1;
stk.emplace_back(-1, -1);
unite(a.first, a.second);
}
};
void solve() {
int n, m, k;
cin >> n >> m >> k;
int cnt22 = 0, cnt33 = 0;
vector<int> here(n * m);
DSU d(n * m);
auto check = [&](int x, int y) {
if (x >= 0 && y >= 0 && x < n - 1 && y < m - 1) {
return here[x * m + y] && here[x * m + y + 1] && here[x * m + m + y] && here[x * m + m + y + 1];
} else {
return false;
}
};
auto check33 = [&](int x, int y) {
return check(x, y) && check(x + 1, y) && check(x, y + 1) && check(x + 1, y + 1);
};
auto count = [&](int x, int y) {
return check(x - 1, y - 1) + check(x, y) + check(x - 1, y) + check(x, y - 1);
};
auto count33 = [&](int x, int y) {
int r = 0;
for (int u = -2; u <= 0; ++u) {
for (int f = -2; f <= 0; ++f) {
r += check33(x + u, y + f);
}
}
return r;
};
int dx[]{0, 0, 1, -1}, dy[]{1, -1, 0, 0};
auto toggle = [&](int x, int y) {
cnt22 -= count(x, y);
cnt33 -= count33(x, y);
int id = x * m + y;
here[id] ^= 1;
for (int t = 0; t < 4; ++t) {
int nx = x + dx[t], ny = y + dy[t];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && here[nx * m + ny]) {
if (here[id]) {
d.update({id, nx * m + ny});
} else {
d.undo();
}
}
}
cnt22 += count(x, y);
cnt33 -= count33(x, y);
};
auto isGood = [&]() {
return d.e == cnt22 + d.t && cnt33 == 0;
};
while (k--) {
int x, y;
cin >> x >> y;
--x, --y;
toggle(x, y);
if (isGood()) {
cout << "1";
} else {
toggle(x, y);
cout << "0";
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
// cin >> test;
while (test--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3752kb
input:
4 3 7 2 1 2 2 2 3 3 1 3 2 4 1 4 2
output:
1111111
result:
ok "1111111"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
3 3 8 1 1 1 2 1 3 2 3 3 3 3 2 3 1 2 1
output:
11111110
result:
ok "11111110"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
10 10 7 9 1 6 6 3 8 8 7 5 10 1 7 1 2
output:
1111111
result:
ok "1111111"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
9 10 50 1 9 1 6 2 3 3 1 7 4 9 4 1 3 2 5 9 2 7 9 5 6 8 10 9 5 5 5 4 10 9 7 5 9 3 2 4 5 1 1 4 7 3 6 2 8 4 3 8 6 5 10 4 8 5 4 7 2 9 6 4 2 7 8 5 2 3 5 9 1 6 1 1 5 9 9 5 8 6 3 8 8 8 4 7 7 7 1 3 7 2 2 3 10 6 9 8 3 7 6
output:
11111111111111111111111111111111111111111111111111
result:
ok "11111111111111111111111111111111111111111111111111"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 5 11 1 5 2 4 1 2 1 3 3 3 3 1 3 4 2 3 1 4 2 1 2 5
output:
11111111111
result:
ok "11111111111"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
7 9 12 7 3 2 3 6 2 2 2 4 2 2 8 5 7 4 4 6 8 2 7 7 2 1 9
output:
111111111111
result:
ok "111111111111"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 4 1 1 2
output:
1
result:
ok "1"
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3536kb
input:
9 8 67 5 5 8 3 9 5 7 4 5 1 9 3 4 2 2 5 1 7 7 8 7 2 8 5 6 1 8 8 4 4 5 4 1 5 3 4 6 7 2 3 3 7 5 7 2 4 2 7 1 3 7 3 2 8 6 6 6 2 6 3 7 5 9 6 7 6 3 6 1 1 6 4 3 1 5 3 8 7 2 1 4 1 8 4 8 6 3 5 5 8 1 6 1 2 4 6 9 4 1 4 3 3 4 8 8 1 4 7 9 8 3 8 6 5 6 8 3 2 2 2 7 1 9 2 4 3 1 8 4 5 8 2 7 7
output:
1111111111111111111111111111111111111111111110010000000000000000000
result:
wrong answer 1st words differ - expected: '111111111111111111111111111111...1111111110010101101000101101101', found: '111111111111111111111111111111...1111111110010000000000000000000'