| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 830031 |
2023-08-18T17:47:08 Z |
Antekb |
Saveit (IOI10_saveit) |
C++17 |
|
6685 ms |
13856 KB |
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define all(x) (x).begin(), (x).end()
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vii = vector<pii>;
void nadaj(vi &V, int x, int b){
for(int i=0; i<b; i++){
V.pb(!!(x&(1<<i)));
}
}
void encode2(vi &ans, int n, int h, int m, int *v1, int *v2){
vi E[n];
int czy[n][h], dist[n][h];
for(int i=0; i<n; i++){
for(int j=0; j<h; j++){
czy[i][j]=(i==j);
dist[i][j]=1e9*(i!=j);
}
}
vi edg;
for(int i=0; i<m; i++){
E[v1[i]].pb(edg.size());
edg.pb(v2[i]);
E[v2[i]].pb(edg.size());
edg.pb(v1[i]);
}
for(int s=0; s<h; s++){
vi V;
V.pb(s);
for(int i=0; i<V.size(); i++){
int v=V[i];
for(int e:E[v]){
if(dist[edg[e]][s]==1e9){
dist[edg[e]][s]=dist[v][s]+1;
V.pb(edg[e]);
}
}
}
}
vi E2[n];
bool spec[n];
for(int v=0; v<n; v++){
int ile=0;
vii V2;
for(int u=0; u<n; u++){
if(u==v)continue;
bool b=1;
for(int i=0; i<h; i++){
if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
b=0;
}
}
if(!b)continue;
b=0;
for(int i=0; i<h; i++){
if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
V2.eb(u, i);
b=1;
}
if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
V2.eb(v, i);
b=1;
}
}
if(b)ile++;
}
sort(all(V2));
V2.resize(unique(all(V2))-V2.begin());
spec[v]=(V2.size()>=100);
if(V2.size()>=100){
for(int u=0; u<n; u++){
if(u==v)continue;
bool b=1;
for(int i=0; i<h; i++){
if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
b=0;
}
}
if(!b)continue;
for(int i=0; i<h; i++){
if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
czy[u][i]=1;
E2[v].pb(u);
}
if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
czy[v][i]=1;
E2[v].pb(u);
}
}
}
}
}
int sum=0;
for(int t=h; t>0; t--){
for(int u=0; u<n; u++){
for(int v=0; v<u; v++){
bool b=1;
for(int i=0; i<h; i++){
if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
b=0;
}
}
if(!b)continue;
int ile=0;
for(int i=0; i<h; i++){
if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
ile++;
}
if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
ile++;
}
}
if(ile==t){
//cerr<<t<<"\n";
sum+=t;
if(2*(u-v)<=n)E2[v].pb(u);
else E2[u].pb(v);
for(int i=0; i<h; i++){
if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
czy[u][i]=1;
}
if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
czy[v][i]=1;
}
}
}
}
}
}
cerr<<sum<<"\n";
for(int i=0; i<n; i++){
sort(E2[i].begin(), E2[i].end());
nadaj(ans, min((int)E2[i].size(), 100), 7);
assert(spec[i]==(E2[i].size()>=100));
if(E2[i].size()>=100){
vi V(n);
for(int u:E2[i]){
V[u]=1;
}
for(int j:V){
nadaj(ans, j, 1);
}
}
else{
for(int u:E2[i]){
nadaj(ans, (u-i+n)%n, 9);
}
}
}
return;
}
void encode3(vi &ans, int n, int h, int m, int *v1, int *v2){
vi E[n];
int czy[n][h], dist[n][h];
for(int i=0; i<n; i++){
for(int j=0; j<h; j++){
czy[i][j]=(i==j);
dist[i][j]=1e9*(i!=j);
}
}
vi edg;
for(int i=0; i<m; i++){
E[v1[i]].pb(edg.size());
edg.pb(v2[i]);
E[v2[i]].pb(edg.size());
edg.pb(v1[i]);
}
for(int s=0; s<h; s++){
vi V;
V.pb(s);
for(int i=0; i<V.size(); i++){
int v=V[i];
for(int e:E[v]){
if(dist[edg[e]][s]==1e9){
dist[edg[e]][s]=dist[v][s]+1;
V.pb(edg[e]);
}
}
}
}
vi E2[n];
int sum=0;
for(int t=h; t>0; t--){
for(int u=0; u<n; u++){
for(int v=0; v<u; v++){
bool b=1;
for(int i=0; i<h; i++){
if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
b=0;
}
}
if(!b)continue;
int ile=0;
for(int i=0; i<h; i++){
if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
ile++;
}
if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
ile++;
}
}
if(ile==t){
//cerr<<t<<"\n";
sum+=t;
if(2*(u-v)<=n)E2[v].pb(u);
else E2[u].pb(v);
for(int i=0; i<h; i++){
if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
czy[u][i]=1;
}
if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
czy[v][i]=1;
}
}
}
}
}
}
cerr<<sum<<"\n";
for(int i=0; i<n; i++){
sort(E2[i].begin(), E2[i].end());
nadaj(ans, min((int)E2[i].size(), 100), 7);
if(E2[i].size()>=100){
vi V(n);
for(int u:E2[i]){
V[u]=1;
}
for(int j:V){
nadaj(ans, j, 1);
}
}
else{
for(int u:E2[i]){
nadaj(ans, (u-i+n)%n, 9);
}
}
}
return;
}
void encode(int n, int h, int m, int *v1, int *v2){
vi V, V2;
encode2(V, n, h, m, v1, v2);
encode3(V2, n, h, m, v1, v2);
if(V2.size()<V.size())V=V2;
for(int i:V){
encode_bit(i);
}
}
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pp pop_back;
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
int czytaj(int b){
int x=0;
for(int i=0; i<b; i++){
x+=(int(decode_bit())<<i);
}
return x;
}
void decode(int n, int h) {
vi E[n];
for(int i=0;i<n; i++){
int k=czytaj(7);
//cerr<<k<<"\n";
if(k>=100){
for(int j=0; j<n; j++){
if(czytaj(1)){
E[i].pb(j);
E[j].pb(i);
}
}
}
else{
while(k--){
int j=czytaj(9);
E[i].pb((j+i)%n);
E[(j+i)%n].pb(i);
}
}
}
for(int s=0; s<h; s++){
vi V;
V.pb(s);
vi dist(n, 1e9);
dist[s]=0;
for(int i=0; i<V.size(); i++){
int v=V[i];
for(int u:E[v]){
if(dist[u]==1e9){
dist[u]=dist[v]+1;
V.pb(u);
}
}
}
for(int i=0; i<n; i++){
hops(s, i, dist[i]);
}
}
}
Compilation message
encoder.cpp: In function 'void encode2(vi&, int, int, int, int*, int*)':
encoder.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
encoder.cpp: In function 'void encode3(vi&, int, int, int, int*, int*)':
encoder.cpp:180:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6685 ms |
13856 KB |
Output is correct - 43000 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4604 KB |
Output is correct - 98 call(s) of encode_bit() |
| 3 |
Correct |
1581 ms |
6572 KB |
Output is correct - 39510 call(s) of encode_bit() |
| 4 |
Correct |
1 ms |
4604 KB |
Output is correct - 116 call(s) of encode_bit() |
| 5 |
Correct |
2760 ms |
6884 KB |
Output is correct - 66717 call(s) of encode_bit() |
| 6 |
Correct |
3210 ms |
7128 KB |
Output is correct - 69064 call(s) of encode_bit() |
| 7 |
Correct |
3781 ms |
7840 KB |
Output is partially correct - 81827 call(s) of encode_bit() |
| 8 |
Correct |
3010 ms |
6460 KB |
Output is correct - 21172 call(s) of encode_bit() |
| 9 |
Correct |
1656 ms |
5652 KB |
Output is correct - 21265 call(s) of encode_bit() |
| 10 |
Correct |
1620 ms |
5704 KB |
Output is correct - 21049 call(s) of encode_bit() |
| 11 |
Correct |
1682 ms |
6112 KB |
Output is correct - 35530 call(s) of encode_bit() |
| 12 |
Correct |
1862 ms |
5448 KB |
Output is correct - 15991 call(s) of encode_bit() |
| 13 |
Correct |
3230 ms |
7428 KB |
Output is correct - 51809 call(s) of encode_bit() |
| 14 |
Correct |
1895 ms |
6004 KB |
Output is correct - 24019 call(s) of encode_bit() |
| 15 |
Correct |
1872 ms |
5980 KB |
Output is correct - 25045 call(s) of encode_bit() |
| 16 |
Correct |
2290 ms |
7244 KB |
Output is correct - 47483 call(s) of encode_bit() |
| 17 |
Correct |
2308 ms |
7024 KB |
Output is correct - 44378 call(s) of encode_bit() |
| 18 |
Correct |
3183 ms |
7492 KB |
Output is correct - 57050 call(s) of encode_bit() |
| 19 |
Correct |
2631 ms |
6792 KB |
Output is correct - 48265 call(s) of encode_bit() |
| 20 |
Correct |
3340 ms |
7904 KB |
Output is correct - 60033 call(s) of encode_bit() |
| 21 |
Correct |
3770 ms |
8472 KB |
Output is correct - 67716 call(s) of encode_bit() |
| 22 |
Correct |
3437 ms |
7972 KB |
Output is correct - 68062 call(s) of encode_bit() |
| 23 |
Correct |
4124 ms |
9072 KB |
Output is correct - 62954 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6685 ms |
13856 KB |
Output is correct - 43000 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4604 KB |
Output is correct - 98 call(s) of encode_bit() |
| 3 |
Correct |
1581 ms |
6572 KB |
Output is correct - 39510 call(s) of encode_bit() |
| 4 |
Correct |
1 ms |
4604 KB |
Output is correct - 116 call(s) of encode_bit() |
| 5 |
Correct |
2760 ms |
6884 KB |
Output is correct - 66717 call(s) of encode_bit() |
| 6 |
Correct |
3210 ms |
7128 KB |
Output is correct - 69064 call(s) of encode_bit() |
| 7 |
Correct |
3781 ms |
7840 KB |
Output is partially correct - 81827 call(s) of encode_bit() |
| 8 |
Correct |
3010 ms |
6460 KB |
Output is correct - 21172 call(s) of encode_bit() |
| 9 |
Correct |
1656 ms |
5652 KB |
Output is correct - 21265 call(s) of encode_bit() |
| 10 |
Correct |
1620 ms |
5704 KB |
Output is correct - 21049 call(s) of encode_bit() |
| 11 |
Correct |
1682 ms |
6112 KB |
Output is correct - 35530 call(s) of encode_bit() |
| 12 |
Correct |
1862 ms |
5448 KB |
Output is correct - 15991 call(s) of encode_bit() |
| 13 |
Correct |
3230 ms |
7428 KB |
Output is correct - 51809 call(s) of encode_bit() |
| 14 |
Correct |
1895 ms |
6004 KB |
Output is correct - 24019 call(s) of encode_bit() |
| 15 |
Correct |
1872 ms |
5980 KB |
Output is correct - 25045 call(s) of encode_bit() |
| 16 |
Correct |
2290 ms |
7244 KB |
Output is correct - 47483 call(s) of encode_bit() |
| 17 |
Correct |
2308 ms |
7024 KB |
Output is correct - 44378 call(s) of encode_bit() |
| 18 |
Correct |
3183 ms |
7492 KB |
Output is correct - 57050 call(s) of encode_bit() |
| 19 |
Correct |
2631 ms |
6792 KB |
Output is correct - 48265 call(s) of encode_bit() |
| 20 |
Correct |
3340 ms |
7904 KB |
Output is correct - 60033 call(s) of encode_bit() |
| 21 |
Correct |
3770 ms |
8472 KB |
Output is correct - 67716 call(s) of encode_bit() |
| 22 |
Correct |
3437 ms |
7972 KB |
Output is correct - 68062 call(s) of encode_bit() |
| 23 |
Correct |
4124 ms |
9072 KB |
Output is correct - 62954 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6685 ms |
13856 KB |
Output is correct - 43000 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4604 KB |
Output is correct - 98 call(s) of encode_bit() |
| 3 |
Correct |
1581 ms |
6572 KB |
Output is correct - 39510 call(s) of encode_bit() |
| 4 |
Correct |
1 ms |
4604 KB |
Output is correct - 116 call(s) of encode_bit() |
| 5 |
Correct |
2760 ms |
6884 KB |
Output is correct - 66717 call(s) of encode_bit() |
| 6 |
Correct |
3210 ms |
7128 KB |
Output is correct - 69064 call(s) of encode_bit() |
| 7 |
Correct |
3781 ms |
7840 KB |
Output is partially correct - 81827 call(s) of encode_bit() |
| 8 |
Correct |
3010 ms |
6460 KB |
Output is correct - 21172 call(s) of encode_bit() |
| 9 |
Correct |
1656 ms |
5652 KB |
Output is correct - 21265 call(s) of encode_bit() |
| 10 |
Correct |
1620 ms |
5704 KB |
Output is correct - 21049 call(s) of encode_bit() |
| 11 |
Correct |
1682 ms |
6112 KB |
Output is correct - 35530 call(s) of encode_bit() |
| 12 |
Correct |
1862 ms |
5448 KB |
Output is correct - 15991 call(s) of encode_bit() |
| 13 |
Correct |
3230 ms |
7428 KB |
Output is correct - 51809 call(s) of encode_bit() |
| 14 |
Correct |
1895 ms |
6004 KB |
Output is correct - 24019 call(s) of encode_bit() |
| 15 |
Correct |
1872 ms |
5980 KB |
Output is correct - 25045 call(s) of encode_bit() |
| 16 |
Correct |
2290 ms |
7244 KB |
Output is correct - 47483 call(s) of encode_bit() |
| 17 |
Correct |
2308 ms |
7024 KB |
Output is correct - 44378 call(s) of encode_bit() |
| 18 |
Correct |
3183 ms |
7492 KB |
Output is correct - 57050 call(s) of encode_bit() |
| 19 |
Correct |
2631 ms |
6792 KB |
Output is correct - 48265 call(s) of encode_bit() |
| 20 |
Correct |
3340 ms |
7904 KB |
Output is correct - 60033 call(s) of encode_bit() |
| 21 |
Correct |
3770 ms |
8472 KB |
Output is correct - 67716 call(s) of encode_bit() |
| 22 |
Correct |
3437 ms |
7972 KB |
Output is correct - 68062 call(s) of encode_bit() |
| 23 |
Correct |
4124 ms |
9072 KB |
Output is correct - 62954 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6685 ms |
13856 KB |
Output is correct - 43000 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4604 KB |
Output is correct - 98 call(s) of encode_bit() |
| 3 |
Correct |
1581 ms |
6572 KB |
Output is correct - 39510 call(s) of encode_bit() |
| 4 |
Correct |
1 ms |
4604 KB |
Output is correct - 116 call(s) of encode_bit() |
| 5 |
Correct |
2760 ms |
6884 KB |
Output is correct - 66717 call(s) of encode_bit() |
| 6 |
Correct |
3210 ms |
7128 KB |
Output is correct - 69064 call(s) of encode_bit() |
| 7 |
Correct |
3781 ms |
7840 KB |
Output is partially correct - 81827 call(s) of encode_bit() |
| 8 |
Correct |
3010 ms |
6460 KB |
Output is correct - 21172 call(s) of encode_bit() |
| 9 |
Correct |
1656 ms |
5652 KB |
Output is correct - 21265 call(s) of encode_bit() |
| 10 |
Correct |
1620 ms |
5704 KB |
Output is correct - 21049 call(s) of encode_bit() |
| 11 |
Correct |
1682 ms |
6112 KB |
Output is correct - 35530 call(s) of encode_bit() |
| 12 |
Correct |
1862 ms |
5448 KB |
Output is correct - 15991 call(s) of encode_bit() |
| 13 |
Correct |
3230 ms |
7428 KB |
Output is correct - 51809 call(s) of encode_bit() |
| 14 |
Correct |
1895 ms |
6004 KB |
Output is correct - 24019 call(s) of encode_bit() |
| 15 |
Correct |
1872 ms |
5980 KB |
Output is correct - 25045 call(s) of encode_bit() |
| 16 |
Correct |
2290 ms |
7244 KB |
Output is correct - 47483 call(s) of encode_bit() |
| 17 |
Correct |
2308 ms |
7024 KB |
Output is correct - 44378 call(s) of encode_bit() |
| 18 |
Correct |
3183 ms |
7492 KB |
Output is correct - 57050 call(s) of encode_bit() |
| 19 |
Correct |
2631 ms |
6792 KB |
Output is correct - 48265 call(s) of encode_bit() |
| 20 |
Correct |
3340 ms |
7904 KB |
Output is correct - 60033 call(s) of encode_bit() |
| 21 |
Correct |
3770 ms |
8472 KB |
Output is correct - 67716 call(s) of encode_bit() |
| 22 |
Correct |
3437 ms |
7972 KB |
Output is correct - 68062 call(s) of encode_bit() |
| 23 |
Correct |
4124 ms |
9072 KB |
Output is correct - 62954 call(s) of encode_bit() |
