QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497771 | #4251. Game | Dimash | 2 | 19ms | 130620kb | C++14 | 2.1kb | 2024-07-29 17:36:21 | 2024-07-29 17:36:22 |
Judging History
answer
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 12;
vector<int> g[N],gr[N];
set<int> L[N * 4],R[N * 4];
int k;
void build(int v = 1,int tl = 0,int tr = k - 1) {
int tm = (tl + tr) >> 1;
for(int i = tl;i <= tr;i++) {
if(i <= tm) {
L[v].insert(i);
}
if(i >= tm) {
R[v].insert(i);
}
}
if(tl == tr) return;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
}
void init(int n, int K) {
k = K;
for(int i = 0;i <= k - 2;i++) {
g[i].push_back(i + 1);
gr[i + 1].push_back(i);
}
build();
}
bool CYC = false;
void add(int x,int y,int v = 1,int tl = 0,int tr = k - 1) {
int tm = (tl + tr) >> 1;
function<void(int)> dfs = [&](int u){
// cout << tm << ' ' << u << "R\n";
R[v].insert(u);
if(L[v].find(u) != L[v].end()) {
CYC = 1;
return;
}
for(int to:g[u]) {
if(R[v].find(to) == R[v].end()) {
dfs(to);
}
if(CYC) return;
}
if(CYC) return;
};
function<void(int)> dfs1 = [&](int u){
if(R[v].find(u) != R[v].end()) {
CYC = 1;
return;
}
L[v].insert(u);
for(int to:gr[u]) {
if(L[v].find(to) == L[v].end()) {
dfs1(to);
}
if(CYC) return;
}
if(CYC) return;
};
if(R[v].find(x) != R[v].end() && R[v].find(y) == R[v].end()) {
dfs(y);
if(CYC) return;
if(tl != tr) {
add(x,y,v+v+1,tm+1,tr);
}
}
if(L[v].find(y) != L[v].end() && L[v].find(x) == L[v].end()) {
dfs1(x);
if(CYC) return;
if(tl != tr) {
add(x,y,v+v,tl,tm);
}
}
}
int add_teleporter(int u, int v) {
if(CYC) return 1;
if(max(u,v) <= k - 1) {
if(u >= v) {
CYC = 1;
return 1;
}
return 0;
}
g[u].push_back(v);
gr[v].push_back(u);
add(u,v);
return CYC;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 2
Accepted
Test #1:
score: 2
Accepted
time: 15ms
memory: 130564kb
input:
1 1 1 893123 893123 -1
output:
0
result:
ok interaction finished.
Test #2:
score: 2
Accepted
time: 15ms
memory: 130620kb
input:
9 9 29 893122 893124 893121 893127 893120 893124 893123 893121 893122 893131 893125 893131 893121 893126 893123 893126 893126 893131 893123 893131 893123 893125 893123 893124 893127 893125 893120 893126 893123 893120 893121 893131 893123 893127 893122 893126 893122 893127 893127 893131 893122 893125...
output:
28
result:
ok interaction finished.
Test #3:
score: 2
Accepted
time: 19ms
memory: 130336kb
input:
100 100 80 893180 893071 893134 893063 893150 893091 893127 893178 893142 893177 893153 893156 893127 893137 893174 893065 893127 893070 893126 893061 893171 893089 893173 893072 893153 893058 893156 893074 893151 893068 893136 893060 893120 893083 893073 893091 893148 893163 893073 893088 893156 89...
output:
80 80 80 59
result:
ok interaction finished.
Test #4:
score: 2
Accepted
time: 15ms
memory: 130388kb
input:
45 45 80 893143 893167 893122 893132 893123 893140 893120 893139 893158 893167 893154 893163 893133 893137 893133 893142 893135 893137 893121 893135 893137 893149 893141 893152 893122 893167 893128 893145 893140 893167 893122 893127 893134 893142 893122 893129 893141 893156 893146 893149 893123 8931...
output:
80 49
result:
ok interaction finished.
Test #5:
score: 2
Accepted
time: 11ms
memory: 130384kb
input:
100 100 80 893169 893058 893132 893065 893143 893068 893153 893167 893152 893182 893138 893162 893129 893163 893146 893164 893134 893180 893142 893167 893144 893059 893132 893064 893135 893091 893164 893068 893123 893179 893126 893060 893136 893140 893179 893081 893139 893181 893120 893057 893172 89...
output:
80 80 80 42
result:
ok interaction finished.
Test #6:
score: 2
Accepted
time: 11ms
memory: 130392kb
input:
100 100 80 893135 893081 893170 893076 893148 893075 893134 893159 893159 893073 893170 893088 893131 893138 893121 893166 893171 893168 893127 893137 893147 893145 893062 893076 893160 893059 893063 893088 893137 893073 893123 893182 893152 893170 893141 893172 893137 893087 893167 893085 893147 89...
output:
80 80 80 37
result:
ok interaction finished.
Test #7:
score: 2
Accepted
time: 15ms
memory: 130384kb
input:
100 100 80 893062 893075 893139 893156 893137 893083 893071 893075 893072 893080 893141 893060 893126 893179 893064 893081 893167 893077 893139 893165 893056 893085 893169 893182 893062 893087 893141 893078 893062 893078 893129 893176 893065 893077 893141 893181 893152 893158 893151 893078 893157 89...
output:
80 80 80 59
result:
ok interaction finished.
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #8:
score: 10
Accepted
time: 12ms
memory: 130364kb
input:
100 10 80 893135 893150 893174 893168 893159 893149 893162 893082 893158 893129 893072 893150 893088 893079 893155 893154 893086 893126 893078 893153 893177 893138 893057 893066 893151 893089 893076 893162 893165 893164 893085 893170 893084 893128 893074 893083 893138 893148 893147 893167 893071 893...
output:
80 31
result:
ok interaction finished.
Test #9:
score: 10
Accepted
time: 11ms
memory: 130372kb
input:
100 10 80 893087 893068 893090 893073 893077 893169 893159 893156 893170 893062 893081 893145 893076 893083 893128 893078 893132 893139 893181 893165 893155 893167 893167 893089 893065 893081 893068 893180 893150 893175 893066 893183 893060 893133 893086 893060 893072 893142 893084 893132 893151 893...
output:
80 10
result:
ok interaction finished.
Test #10:
score: 0
Wrong Answer
time: 15ms
memory: 130312kb
input:
100 10 80 893136 893078 893085 893075 893173 893143 893132 893066 893066 893074 893149 893080 893152 893148 893179 893146 893174 893137 893082 893077 893140 893082 893080 893134 893171 893149 893070 893161 893087 893132 893168 893059 893086 893085 893159 893153 893143 893173 893167 893140 893062 893...
output:
80 26
result:
wrong answer Wrong Answer [1]
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%