Submission #830026

#TimeUsernameProblemLanguageResultExecution timeMemory
830026AntekbSaveit (IOI10_saveit)C++17
Compilation error
0 ms0 KiB
#include "grader.h" #include "encoder.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>; 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 (stderr)

encoder.cpp: In function 'void encode2(vi&, int, int, int, int*, int*)':
encoder.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~
encoder.cpp:49:3: error: 'vii' was not declared in this scope; did you mean 'pii'?
   49 |   vii V2;
      |   ^~~
      |   pii
encoder.cpp:62:6: error: 'V2' was not declared in this scope; did you mean 'E2'?
   62 |      V2.eb(u, i);
      |      ^~
      |      E2
encoder.cpp:66:6: error: 'V2' was not declared in this scope; did you mean 'E2'?
   66 |      V2.eb(v, i);
      |      ^~
      |      E2
encoder.cpp:72:12: error: 'V2' was not declared in this scope; did you mean 'E2'?
   72 |   sort(all(V2));
      |            ^~
      |            E2
encoder.cpp:72:8: error: 'all' was not declared in this scope; did you mean 'std::filesystem::perms::all'?
   72 |   sort(all(V2));
      |        ^~~
      |        std::filesystem::perms::all
In file included from /usr/include/c++/10/filesystem:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from encoder.cpp:3:
/usr/include/c++/10/bits/fs_fwd.h:148:7: note: 'std::filesystem::perms::all' declared here
  148 |       all  =  0777,
      |       ^~~
encoder.cpp: In function 'void encode3(vi&, int, int, int, int*, int*)':
encoder.cpp:176:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |   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++){
      |                ~^~~~~~~~~