QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #878222 | #8593. Coin | hirayuu_qoj | 32 | 229ms | 4480kb | C++20 | 9.9kb | 2025-02-01 14:13:50 | 2025-02-01 14:13:51 |
Judging History
answer
#line 2 "Template/Template.hpp"
#include <bits/stdc++.h>
using namespace std;
#line 8 "Template/InOut.hpp"
inline void scan() {}
inline void scan(int32_t &a) { std::cin >> a; }
inline void scan(uint32_t &a) { std::cin >> a; }
inline void scan(int64_t &a) { std::cin >> a; }
inline void scan(uint64_t &a) { std::cin >> a; }
inline void scan(char &a) { std::cin >> a; }
inline void scan(float &a) { std::cin >> a; }
inline void scan(double &a) { std::cin >> a; }
inline void scan(long double &a) { std::cin >> a; }
inline void scan(std::vector<bool> &vec) {
for (int32_t i = 0; i < vec.size(); i++) {
int a;
scan(a);
vec[i] = a;
}
}
inline void scan(std::string &a) { std::cin >> a; }
template <class T>
inline void scan(std::vector<T> &vec);
template <class T, size_t size>
inline void scan(std::array<T, size> &vec);
template <class T, class L>
inline void scan(std::pair<T, L> &p);
template <class T, size_t size>
inline void scan(T (&vec)[size]);
template <class T>
inline void scan(std::vector<T> &vec) {
for (auto &i : vec) scan(i);
}
template <class T>
inline void scan(std::deque<T> &vec) {
for (auto &i : vec) scan(i);
}
template <class T, size_t size>
inline void scan(std::array<T, size> &vec) {
for (auto &i : vec) scan(i);
}
template <class T, class L>
inline void scan(std::pair<T, L> &p) {
scan(p.first);
scan(p.second);
}
template <class T, size_t size>
inline void scan(T (&vec)[size]) {
for (auto &i : vec) scan(i);
}
template <class T>
inline void scan(T &a) {
std::cin >> a;
}
inline void in() {}
template <class Head, class... Tail>
inline void in(Head &head, Tail &...tail) {
scan(head);
in(tail...);
}
inline void print() { std::cout << ' '; }
inline void print(const bool &a) { std::cout << a; }
inline void print(const int32_t &a) { std::cout << a; }
inline void print(const uint32_t &a) { std::cout << a; }
inline void print(const int64_t &a) { std::cout << a; }
inline void print(const uint64_t &a) { std::cout << a; }
inline void print(const char &a) { std::cout << a; }
inline void print(const char a[]) { std::cout << a; }
inline void print(const float &a) { std::cout << a; }
inline void print(const double &a) { std::cout << a; }
inline void print(const long double &a) { std::cout << a; }
inline void print(const std::string &a) {
for (auto &&i : a) print(i);
}
template <class T>
inline void print(const std::vector<T> &vec);
template <class T, size_t size>
inline void print(const std::array<T, size> &vec);
template <class T, class L>
inline void print(const std::pair<T, L> &p);
template <class T, size_t size>
inline void print(const T (&vec)[size]);
template <class T>
inline void print(const std::vector<T> &vec) {
if (vec.empty()) return;
print(vec[0]);
for (auto i = vec.begin(); ++i != vec.end();) {
std::cout << ' ';
print(*i);
}
}
template <class T>
inline void print(const std::deque<T> &vec) {
if (vec.empty()) return;
print(vec[0]);
for (auto i = vec.begin(); ++i != vec.end();) {
std::cout << ' ';
print(*i);
}
}
template <class T, size_t size>
inline void print(const std::array<T, size> &vec) {
print(vec[0]);
for (auto i = vec.begin(); ++i != vec.end();) {
std::cout << ' ';
print(*i);
}
}
template <class T, class L>
inline void print(const std::pair<T, L> &p) {
print(p.first);
std::cout << ' ';
print(p.second);
}
template <class T, size_t size>
inline void print(const T (&vec)[size]) {
print(vec[0]);
for (auto i = vec; ++i != end(vec);) {
std::cout << ' ';
print(*i);
}
}
template <class T>
inline void print(const T &a) {
std::cout << a;
}
inline void out() { std::cout << '\n'; }
template <class T>
inline void out(const T &t) {
print(t);
std::cout << '\n';
}
template <class Head, class... Tail>
inline void out(const Head &head, const Tail &...tail) {
print(head);
std::cout << ' ';
out(tail...);
}
inline void Yes(bool i = true) { out(i ? "Yes" : "No"); }
inline void No(bool i = true) { out(i ? "No" : "Yes"); }
inline void Takahashi(bool i = true) { out(i ? "Takahashi" : "Aoki"); }
inline void Aoki(bool i = true) { out(i ? "Aoki" : "Takahashi"); }
inline void Alice(bool i = true) { out(i ? "Alice" : "Bob"); }
inline void Bob(bool i = true) { out(i ? "Bob" : "Alice"); }
inline void First(bool i = true) { out(i ? "First" : "Second"); }
inline void Second(bool i = true) { out(i ? "Second" : "First"); }
inline void Possible(bool i = true) { out(i ? "Possible" : "Impossible"); }
inline void Impossible(bool i = true) { out(i ? "Impossible" : "Possible"); }
inline void fls() { std::flush(std::cout); }
struct IOsetup {
IOsetup() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(16);
}
} iosetup;
#line 9 "Template/Util.hpp"
using ll = int64_t;
using ld = long double;
using ull = uint64_t;
using uint = uint32_t;
using pll = std::pair<ll, ll>;
using pii = std::pair<int32_t, int32_t>;
using vl = std::vector<ll>;
using vvl = std::vector<std::vector<ll>>;
using pdd = std::pair<ld, ld>;
using tuplis = std::array<ll, 3>;
template <class T>
using pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr ll LINF = (1LL << 62) - (1LL << 31);
constexpr int32_t INF = INT_MAX >> 1;
constexpr ll MINF = 1LL << 40;
constexpr ld DINF = std::numeric_limits<ld>::infinity();
constexpr int32_t MODD = 1000000007;
constexpr int32_t MOD = 998244353;
constexpr ld EPS = 1e-9;
constexpr ld PI = 3.1415926535897932;
const ll four[] = {0, 1, 0, -1, 0};
const ll eight[] = {0, 1, 1, 0, -1, -1, 1, -1, 0};
template <class T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
} else
return false;
}
template <class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
} else
return false;
}
template <class T>
ll sum(const T &a) {
return accumulate(std::begin(a), std::end(a), 0LL);
}
template <class T>
ld dsum(const T &a) {
return accumulate(std::begin(a), std::end(a), 0.0L);
}
template <class T>
auto min(const T &a) {
return *min_element(std::begin(a), std::end(a));
}
template <class T>
auto max(const T &a) {
return *max_element(std::begin(a), std::end(a));
}
#line 1 "Template/Macro.hpp"
#define _overload3(_1, _2, _3, name, ...) name
#define _overload4(_1, _2, _3, _4, name, ...) name
#define _rep1(i, n) for (int64_t i = 0; i < (n); i++)
#define _rep2(i, a, b) for (int64_t i = (a); i < (b); i++)
#define _rep3(i, a, b, c) for (int64_t i = (a); i < (b); i += (c))
#define rep(...) _overload4(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__)
#define _rrep1(i, n) for (int64_t i = (n) - 1; i >= 0; i--)
#define _rrep2(i, a, b) for (int64_t i = (b) - 1; i >= (a); i--)
#define rrep(...) _overload3(__VA_ARGS__, _rrep2, _rrep1)(__VA_ARGS__)
#define each(i, ...) for (auto&& i : __VA_ARGS__)
#define all(i) std::begin(i), std::end(i)
#define rall(i) std::rbegin(i), std::rend(i)
#define len(x) ((int64_t)(x).size())
#define fi first
#define se second
#define uniq(x) x.erase(unique(all(x)), std::end(x))
#define vec(type, name, ...) vector<type> name(__VA_ARGS__);
#define vv(type, name, h, ...) std::vector<std::vector<type>> name(h, std::vector<type>(__VA_ARGS__));
#define INT(...) int32_t __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) int64_t __VA_ARGS__; in(__VA_ARGS__)
#define ULL(...) uint64_t __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) std::string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) long double __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type, name, size) std::vector<type> name(size); in(name)
#define VV(type, name, h, w) std::vector<std::vector<type>> name(h, std::vector<type>(w)); in(name)
#line 8 "Template/Template.hpp"
int main(){
LL(n,m);
if(n<=1000&&m<=4000){
vv(ll,gr,n);
VEC(pll,edge,m);
rep(i,m){edge[i].fi--;edge[i].se--;}
vv(tuplis,bs,m+1);
rep(i,n){
bs[(-1+m)/2].push_back({i,-1,m});
}
vec(ll,ans,n);
rep(_,14){
vv(ll,str,n);
vv(ll,rev,n);
rep(i,m){
str[edge[i].fi].emplace_back(edge[i].se);
rev[edge[i].se].emplace_back(edge[i].fi);
each(info,bs[i]){
ll id,ng,ok;
id=info[0];ng=info[1];ok=info[2];
vec(ll,vis,n,-1);
queue<ll> que;
que.push(id);
vis[id]=0;
while(!que.empty()){
ll np=que.front();que.pop();
each(j,str[np]){
if(vis[j]==-1){
vis[j]=0;
que.push(j);
}
}
}
que.push(id);
vis[id]=0;
while(!que.empty()){
ll np=que.front();que.pop();
each(j,rev[np]){
if(vis[j]==-1){
vis[j]=0;
que.push(j);
}
}
}
bool flg=true;
rep(j,n){
if(vis[j]==-1){
flg=false;
break;
}
}
if(flg){
ok=i;
}
else{
ng=i;
}
if(ok-ng==1){
ans[id]=ok;
}
else{
bs[(ok+ng)/2].push_back({id,ng,ok});
}
}
bs[i].clear();
}
}
rep(i,n){
if(ans[i]==m)ans[i]=-2;
ans[i]++;
}
out(ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 0ms
memory: 3712kb
input:
4 4 2 4 3 1 4 1 2 3
output:
3 4 -1 -1
result:
ok ac
Test #2:
score: 6
Accepted
time: 1ms
memory: 3712kb
input:
6 8 1 5 5 4 6 2 2 5 4 3 6 1 6 5 2 1
output:
8 8 5 5 5 6
result:
ok ac
Test #3:
score: 6
Accepted
time: 0ms
memory: 3712kb
input:
2 1 1 2
output:
1 1
result:
ok ac
Test #4:
score: 6
Accepted
time: 0ms
memory: 3712kb
input:
6 12 1 5 5 4 6 2 2 5 4 3 6 5 1 5 1 5 2 4 6 3 1 3 4 3
output:
-1 -1 5 5 5 -1
result:
ok ac
Test #5:
score: 6
Accepted
time: 1ms
memory: 3712kb
input:
7 20 1 6 6 3 1 4 1 5 1 7 1 2 1 5 2 3 4 5 7 2 2 4 5 3 6 3 1 3 4 3 7 5 2 6 4 6 7 2 7 5
output:
6 17 12 18 -1 -1 17
result:
ok ac
Test #6:
score: 6
Accepted
time: 0ms
memory: 3712kb
input:
7 20 5 6 1 3 3 6 4 1 7 4 2 5 4 3 2 6 7 5 4 6 2 6 2 1 4 5 1 3 1 5 7 1 7 6 4 1 7 6 3 6
output:
15 -1 -1 -1 -1 6 -1
result:
ok ac
Test #7:
score: 6
Accepted
time: 1ms
memory: 3584kb
input:
7 20 7 6 4 5 6 4 3 6 4 1 6 2 3 5 5 2 7 6 1 2 3 6 6 4 7 1 6 1 7 1 4 5 3 6 3 5 4 5 3 1
output:
-1 10 -1 8 -1 6 -1
result:
ok ac
Subtask #2:
score: 16
Accepted
Dependency #1:
100%
Accepted
Test #8:
score: 16
Accepted
time: 0ms
memory: 3712kb
input:
20 100 5 20 4 5 18 16 1 13 14 9 11 19 6 4 7 20 16 11 8 13 4 5 16 9 12 14 7 12 11 3 9 11 9 11 13 6 3 10 12 9 13 4 20 12 13 6 18 11 5 7 5 7 15 18 12 15 17 13 15 18 3 2 11 2 11 2 15 19 4 19 14 19 14 9 17 3 1 18 8 10 16 19 1 6 7 2 5 12 1 18 8 20 5 18 8 5 4 16 1 15 5 19 18 19 17 10 1 10 17 3 10 2 3 10 17...
output:
-1 -1 -1 31 31 31 31 -1 31 -1 31 31 31 -1 71 -1 -1 -1 -1 31
result:
ok ac
Test #9:
score: 16
Accepted
time: 2ms
memory: 3712kb
input:
100 400 87 45 42 17 9 81 65 10 8 82 76 48 39 73 21 58 76 30 76 92 74 76 99 90 38 50 86 74 75 52 8 2 80 55 20 95 66 60 78 82 10 18 22 59 23 17 63 76 56 51 38 10 50 65 41 28 64 77 59 53 100 66 38 84 23 47 17 9 45 75 41 28 33 41 8 78 2 95 3 11 40 15 60 63 23 17 82 2 61 44 44 16 77 34 100 66 96 99 68 12...
output:
-1 -1 187 -1 183 -1 -1 -1 183 -1 187 -1 -1 187 183 187 183 -1 -1 -1 -1 183 -1 183 -1 -1 183 183 -1 -1 -1 -1 187 187 -1 -1 187 183 183 183 -1 -1 183 187 183 188 -1 -1 -1 -1 183 -1 183 183 -1 -1 -1 -1 183 -1 187 -1 -1 187 -1 187 -1 -1 -1 -1 -1 -1 183 -1 183 187 187 -1 188 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok ac
Subtask #3:
score: 10
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #10:
score: 10
Accepted
time: 229ms
memory: 4352kb
input:
1000 4000 619 298 211 477 584 418 812 280 978 268 280 345 715 364 73 664 915 819 535 28 110 959 384 663 773 315 792 250 374 80 134 202 779 416 613 334 318 756 21 812 424 997 664 277 151 963 299 438 955 988 532 653 521 43 121 20 902 849 237 305 272 893 325 792 469 549 891 531 612 810 294 256 188 990 ...
output:
-1 1981 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1980 1981 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1980 1977 1981 -1 -1 -1 -1 1981 -1 -1 -1 -1 -1 -1 -1 1980 -1 -1 1981 1977 -1 -1 -1 -1 -1 -1 -1 -1 -1 1981 -1 -1 -1 -1 -1 -1 1981 -1 -1 -1 1981 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1977 -1 -1 -1 -1 -1...
result:
ok ac
Test #11:
score: 10
Accepted
time: 185ms
memory: 4480kb
input:
1000 4000 229 403 665 867 715 618 306 900 423 567 515 288 39 754 782 321 516 969 432 89 304 726 837 39 648 991 870 369 84 681 864 41 682 940 565 914 724 763 694 112 969 815 864 41 975 868 662 803 707 465 905 791 116 115 823 578 949 588 589 522 775 447 795 130 366 456 993 910 187 396 102 774 143 90 9...
output:
1976 -1 -1 1961 1976 1976 -1 -1 -1 -1 1973 -1 1961 -1 -1 1976 -1 -1 -1 1976 -1 -1 1961 -1 1976 1976 1961 1961 -1 1961 -1 -1 1961 -1 1976 -1 -1 -1 -1 -1 -1 -1 -1 1976 -1 -1 1973 -1 1976 -1 1961 -1 1976 -1 -1 -1 -1 -1 -1 -1 1976 -1 1976 1976 1976 -1 1976 1961 1976 -1 -1 -1 -1 -1 1973 -1 1976 -1 1976 1...
result:
ok ac
Test #12:
score: 10
Accepted
time: 154ms
memory: 4352kb
input:
1000 4000 693 317 927 745 607 353 336 456 182 240 100 824 252 317 88 828 436 714 833 621 533 704 63 735 522 518 900 283 135 829 627 459 601 176 876 806 573 140 380 898 870 795 990 876 943 148 500 462 808 486 920 463 794 7 531 181 60 105 497 875 859 469 997 575 706 838 296 194 453 793 310 673 771 307...
output:
1998 1998 -1 -1 -1 -1 1998 1998 -1 1998 -1 1998 1998 -1 1987 -1 1998 1998 -1 -1 -1 -1 -1 1998 1998 1998 -1 -1 -1 1998 -1 1998 -1 -1 -1 -1 1998 -1 1998 -1 1998 -1 1998 -1 -1 1998 1998 1998 1998 -1 1998 1998 1998 -1 1987 1998 -1 1998 1998 1998 -1 -1 1998 -1 -1 1998 -1 1998 1998 1998 1998 1998 -1 1987 ...
result:
ok ac
Subtask #4:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 3584kb
input:
10000 24156 6770 9800 71 3709 5373 2058 9145 5993 9973 456 1562 628 839 3483 9354 9169 7105 7062 4434 4044 2147 534 7337 1981 719 3853 8205 8198 1286 7343 246 4189 1324 8878 547 3468 2219 8650 7265 5823 6382 5720 6219 1258 8893 466 5615 9147 7763 7160 3652 6512 7594 7169 235 1287 6487 2049 6894 853 ...
output:
result:
wrong output format Unexpected end of file - int32 expected