QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#155673 | #7119. Longest Trip | bulijiojiodibuliduo# | 0 | 1ms | 3796kb | C++17 | 2.8kb | 2023-09-02 00:15:15 | 2023-09-02 00:15:15 |
Judging History
answer
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(1);
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
vector<int> longest_trip(int n, int D) {
VI ch;
vector<set<int>> notc(n);
VI ord(n);
iota(all(ord),0);
shuffle(all(ord),mrand);
map<PII,bool> cache;
auto query=[&](int u,int v) {
u=ord[u]; v=ord[v];
if (cache.count(mp(u,v))) return cache[mp(u,v)];
bool w=are_connected(VI{u},VI{v});
//printf("cnm %d %d %d\n",u,v,w);
if (!w) notc[u].insert(v),notc[v].insert(u);
return cache[mp(u,v)]=cache[mp(v,u)]=w;
};
VI unv;
//puts("??");
rep(i,0,3) rep(j,i+1,3) if (query(i,j)) {
ch.pb(i); ch.pb(j);
rep(k,0,n) if (k!=i&&k!=j) unv.pb(k);
goto init;
}
assert(0);
//puts("???");
init:;
shuffle(all(unv),mrand);
for (auto w:unv) {
for (auto x:ch) printf("%d ",x); puts("ch!");
if (rnd(2)) reverse(all(ch));
int u=ch[0],v=ch[SZ(ch)-1];
if (query(v,w)) {
ch.pb(w); continue;
} else if (query(u,w)) {
ch.insert(ch.begin(),w); continue;
} else {
cache[mp(u,v)]=cache[mp(v,u)]=true;
int md=-1;
for (auto x:notc[u]) if (x!=v&&x!=u&&x!=w) md=x;
for (auto x:notc[v]) if (x!=v&&x!=u&&x!=w) md=x;
if (md==-1) {
int l=0,r=SZ(ch)-2;
while (l+1<r) {
int mid=(l+r)>>1;
VI ww(ch.begin(),ch.begin()+mid+1);
if (are_connected(VI{w},ww)) {
r=mid;
} else {
l=mid;
for (auto vv:ww) {
cache[mp(w,vv)]=cache[mp(vv,w)]=true;
notc[w].insert(vv);
notc[vv].insert(w);
}
}
}
md=ch[r];
}
cache[mp(w,md)]=cache[mp(md,w)]=true;
rotate(ch.begin(),find(all(ch),w),ch.end());
ch.insert(ch.begin(),w);
}
}
return ch;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3796kb
input:
341 3 3 1
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 0 0 1 ch! 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 2
result:
wrong answer Secret mismatch (possible tampering with the output).
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 3704kb
input:
341 3 2 1
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 0 0 1 ch! 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 2
result:
wrong answer Secret mismatch (possible tampering with the output).
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 1ms
memory: 3656kb
input:
341 3 1 1
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 0 0 1 ch! 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 2
result:
wrong answer Secret mismatch (possible tampering with the output).
Subtask #4:
score: 0
Wrong Answer
Test #83:
score: 0
Wrong Answer
time: 1ms
memory: 3640kb
input:
341 3 1 1
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 0 0 1 ch! 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 2
result:
wrong answer Secret mismatch (possible tampering with the output).