| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 427389 |
2021-06-14T14:49:42 Z |
kai824 |
City (JOI17_city) |
C++17 |
|
655 ms |
51720 KB |
#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> adjl[250005];
ll pre[250005],sub[250005],nex;
ll cnts[250005];
void init(){
for(int i=1;i<250001;i++){
cnts[i]=cnts[i-1]+(250001-i);
}
}
ll convert(int x,int y){//returns no. of smaller pairs...
y-=x;
assert(cnts[x]+y<cnts[x+1]);
return cnts[x]+y;
}
void dfs(int node,int p=-1){
pre[node]=nex++;
for(int x:adjl[node]){
if(x==p)continue;
dfs(x,node);
}
sub[node]=nex-1;
// cout<<node<<' '<<pre[node]<<' '<<sub[node]<<'\n';
Code(node,convert(pre[node],sub[node]));
}
void Encode(int n, int a[], int b[]){
init();
for(int i=0;i+1<n;i++){
adjl[a[i]].push_back(b[i]);
adjl[b[i]].push_back(a[i]);
}
dfs(0);
//Code(i, 0LL): node, label...
}
#include "Device.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt[250005];
void InitDevice(){
cnt[0]=0;
for(int i=1;i<250001;i++){
cnt[i]=cnt[i-1]+(250001-i);
}
}
void unpack(ll x,int&a, int&b){
for(int i=0;i<10;i++){//check smol numbers manually...
if(x>=cnt[i]){
a=i;
b=x-cnt[i];
}else break;
}
a=upper_bound(cnt,cnt+250001,x)-cnt-1;
b=x-cnt[a]+a;
//cout<<x<<' '<<a<<' '<<b<<'\n';
}
int Answer(long long s, long long t){
int p1,p2,s1,s2;
unpack(s,p1,s1);
unpack(t,p2,s2);
if(p1<p2 && p2<=s1)return 1;
if(p2<p1 && p1<=s2)return 0;
return 2;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
10492 KB |
Output is correct |
| 2 |
Correct |
9 ms |
10512 KB |
Output is correct |
| 3 |
Correct |
8 ms |
10504 KB |
Output is correct |
| 4 |
Correct |
8 ms |
10504 KB |
Output is correct |
| 5 |
Correct |
9 ms |
10516 KB |
Output is correct |
| 6 |
Correct |
9 ms |
10496 KB |
Output is correct |
| 7 |
Correct |
7 ms |
10504 KB |
Output is correct |
| 8 |
Correct |
8 ms |
10480 KB |
Output is correct |
| 9 |
Correct |
8 ms |
10464 KB |
Output is correct |
| 10 |
Correct |
8 ms |
10484 KB |
Output is correct |
| 11 |
Correct |
9 ms |
10504 KB |
Output is correct |
| 12 |
Correct |
9 ms |
10496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
235 ms |
23144 KB |
Output is correct - L = 174506049 |
| 2 |
Correct |
242 ms |
23024 KB |
Output is correct - L = 174256747 |
| 3 |
Correct |
227 ms |
22492 KB |
Output is correct - L = 174506049 |
| 4 |
Correct |
222 ms |
22496 KB |
Output is correct - L = 174506049 |
| 5 |
Partially correct |
638 ms |
51720 KB |
Output is partially correct - L = 31250124999 |
| 6 |
Partially correct |
610 ms |
50656 KB |
Output is partially correct - L = 31250124999 |
| 7 |
Partially correct |
612 ms |
50656 KB |
Output is partially correct - L = 31250124999 |
| 8 |
Partially correct |
624 ms |
50448 KB |
Output is partially correct - L = 31250124999 |
| 9 |
Partially correct |
519 ms |
51368 KB |
Output is partially correct - L = 31250124999 |
| 10 |
Partially correct |
526 ms |
51312 KB |
Output is partially correct - L = 31250124999 |
| 11 |
Partially correct |
517 ms |
51296 KB |
Output is partially correct - L = 31250124999 |
| 12 |
Partially correct |
538 ms |
51360 KB |
Output is partially correct - L = 31250124999 |
| 13 |
Partially correct |
555 ms |
51088 KB |
Output is partially correct - L = 31250124999 |
| 14 |
Partially correct |
586 ms |
50852 KB |
Output is partially correct - L = 31250124999 |
| 15 |
Correct |
237 ms |
24000 KB |
Output is correct - L = 174506049 |
| 16 |
Correct |
232 ms |
24048 KB |
Output is correct - L = 174506049 |
| 17 |
Correct |
238 ms |
23940 KB |
Output is correct - L = 174506049 |
| 18 |
Partially correct |
655 ms |
50828 KB |
Output is partially correct - L = 31250124999 |
| 19 |
Partially correct |
601 ms |
50800 KB |
Output is partially correct - L = 31250124999 |
| 20 |
Partially correct |
606 ms |
50836 KB |
Output is partially correct - L = 31250124999 |
| 21 |
Partially correct |
595 ms |
50900 KB |
Output is partially correct - L = 31250124999 |
| 22 |
Partially correct |
642 ms |
50836 KB |
Output is partially correct - L = 31250124999 |
| 23 |
Partially correct |
604 ms |
50780 KB |
Output is partially correct - L = 31250124999 |
| 24 |
Partially correct |
600 ms |
50772 KB |
Output is partially correct - L = 31250124999 |
| 25 |
Partially correct |
651 ms |
50720 KB |
Output is partially correct - L = 31250124999 |
| 26 |
Partially correct |
608 ms |
50736 KB |
Output is partially correct - L = 31250124999 |
| 27 |
Partially correct |
643 ms |
50644 KB |
Output is partially correct - L = 31250124999 |
