QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #426723 | #5029. 在路上 | Richard_whr | Compile Error | / | / | C++20 | 2.0kb | 2024-05-31 18:03:50 | 2024-05-31 18:03:50 |
Judging History
answer
#include”path.h"
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,m,L,R,szl,szr,wc;
int bel[N],p[N];
vector<int> link,ctr;
mt19937 rnd(time(0));
int ask(int a,int b,int c)
{
return 0;
}
int rand(int l,int r)
{
return rnd()%(r-l+1)+l;
}
int get_fa(int u)
{
if(bel[u]==u) return u;
int fa=0;
for(auto x:link)
{
if(!fa) fa=x;
else fa=ask(fa,u,x);
}
return fa;
}
bool check(int x,int lc,int rc)
{
int cnt=0,now=0;
if(lc!=rc) cnt=abs(lc-rc),now=lc>rc?L:R;
for(auto u:ctr)
{
if(u==x||bel[u]!=-1) continue;
if(!now||ask(now,x,u)!=x) now=(!now)?u:now,cnt++;
else if((--cnt)==0) now=0;
}
if(!now||now==L||now==R) return true;
cnt=0;
for(auto u:ctr)
{
if(u==x||bel[u]!=-1) continue;
if(u==now||ask(now,x,u)!=x) cnt++;
}
return cnt*2<=n;
}
int solve()
{
if(L==R||ctr.size()==0) return 0;
vector<int> vec;vec=ctr;
ctr.clear(),link.clear();
for(auto x:vec)
{
if(x==L||x==R) continue;
bel[x]=ask(L,x,R);
if(bel[x]==L) szl++;
else if(bel[x]==R) szr++;
else if(bel[x]==x) link.push_back(x),ctr.push_back(x);
else ctr.push_back(x);
}
if(szl*2>n||szr*2>n) return 0;
int nw=get_fa(ctr[rand(0,ctr.size()-1)]);
int lc=szl,rc=szr;
for(auto x:ctr)
{
if(x==nw) continue;
if(ask(x,L,nw)!=nw) bel[x]=0,lc++;
else if(ask(x,R,nw)!=nw) bel[x]=1,rc++;
else bel[x]=-1;
}
if(lc*2<=n&&rc*2<=n&&check(nw,lc,rc)) return nw;
if(lc>rc) R=nw,szr++;
else L=nw,szl++;
return solve();
}
int centroid(int id,int N,int M)
{
n=N,m=M;
if(id==5)
{
int a=1,b=2;
p[1]=1,p[2]=2;
for(int i=3;i<=n;i++)
{
p[i]=i;
int mid=ask(a,b,i);
if(mid==a) a=i;
else if(mid==b) b=i;
}
nth_element(p+1,p+n/2+1,p+n+1,[=](const int&x,const int&y){return ask(a,x,y)!=x;});
return p[n/2+1];
}
if(n==3) return ask(1,2,3);
while(true)
{
link.clear();
L=rand(1,n),R=rand(1,n);
for(int u=1;u<=n;u++)
{
if(u!=L&&u!=R) ctr.push_back(u);
}
szl=szr=1;
if((wc=solve())) return wc;
}
}
详细
implementer.cpp: In function ‘int main()’:
implementer.cpp:60:14: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
60 | fread(Interactor::rbuf,1,50000000,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:1:2: error: extended character ” is not valid in an identifier
1 | #include”path.h"
| ^
answer.code:1:2: error: invalid preprocessing directive #include\U0000201dpath
1 | #include”path.h"
| ^~~~~~~~~~~~
answer.code:1:16: warning: missing terminating " character
1 | #include”path.h"
| ^
answer.code:7:13: error: ‘std::vector<int> link’ redeclared as different kind of entity
7 | vector<int> link,ctr;
| ^~~~
In file included from /usr/include/c++/13/bits/atomic_wait.h:44,
from /usr/include/c++/13/bits/atomic_base.h:42,
from /usr/include/c++/13/bits/shared_ptr_atomic.h:33,
from /usr/include/c++/13/memory:81,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:56,
from answer.code:2:
/usr/include/unistd.h:789:12: note: previous declaration ‘int link(const char*, const char*)’
789 | extern int link (const char *__from, const char *__to)
| ^~~~
answer.code: In function ‘int get_fa(int)’:
answer.code:24:20: error: ‘begin’ was not declared in this scope
24 | for(auto x:link)
| ^~~~
answer.code:24:20: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166:
/usr/include/c++/13/valarray:1232:5: note: ‘std::begin’
1232 | begin(const valarray<_Tp>& __va) noexcept
| ^~~~~
In file included from /usr/include/c++/13/bits/ranges_algobase.h:38,
from /usr/include/c++/13/bits/ranges_algo.h:38,
from /usr/include/c++/13/algorithm:63,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/bits/ranges_base.h:489:44: note: ‘std::ranges::__cust::begin’
489 | inline constexpr __cust_access::_Begin begin{};
| ^~~~~
In file included from /usr/include/c++/13/filesystem:50,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:200:
/usr/include/c++/13/bits/fs_dir.h:607:3: note: ‘std::filesystem::__cxx11::begin’
607 | begin(recursive_directory_iterator __iter) noexcept
| ^~~~~
In file included from /usr/include/c++/13/bits/stl_iterator_base_types.h:71,
from /usr/include/c++/13/bits/stl_algobase.h:65,
from /usr/include/c++/13/algorithm:60:
/usr/include/c++/13/bits/iterator_concepts.h:969:10: note: ‘std::ranges::__cust_access::begin’
969 | void begin(const auto&) = delete;
| ^~~~~
answer.code:24:20: error: ‘end’ was not declared in this scope
24 | for(auto x:link)
| ^~~~
answer.code:24:20: note: suggested alternatives:
/usr/include/c++/13/valarray:1259:5: note: ‘std::end’
1259 | end(const valarray<_Tp>& __va) noexcept
| ^~~
/usr/include/c++/13/bits/ranges_base.h:490:42: note: ‘std::ranges::__cust::end’
490 | inline constexpr __cust_access::_End end{};
| ^~~
/usr/include/c++/13/bits/fs_dir.h:612:3: note: ‘std::filesystem::__cxx11::end’
612 | end(recursive_directory_iterator) noexcept
| ^~~
/usr/include/c++/13/bits/ranges_base.h:137:10: note: ‘std::ranges::__cust_access::end’
137 | void end(const auto&) = delete;
| ^~~
answer.code: In function ‘int solve()’:
answer.code:56:26: error: request for member ‘clear’ in ‘link’, which is of non-class type ‘int(const char*, const char*) noexcept’
56 | ctr.clear(),link.clear();
| ^~~~~
answer.code:63:41: error: request for member ‘push_back’ in ‘link’, which is of non-class type ‘int(const char*, const char*) noexcept’
63 | else if(bel[x]==x) link.push_back(x),ctr.push_back(x);
| ^~~~~~~~~
answer.code: In function ‘int centroid(int, int, int)’:
answer.code:102:22: error: request for member ‘clear’ in ‘link’, which is of non-class type ‘int(const char*, const char*) noexcept’
102 | link.clear();
| ^~~~~