oj.uz

답안 #829996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829996 2023-08-18T17:05:13 Z Antekb 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 5349 ms 13764 KB 
#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];
	for(int v=0; v<n; v++){
		int ile=0;
		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){
					b=1;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					b=1;
				}
			}
			if(b)ile++;
		}
		if(ile>=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-v);
				else E2[u].pb(v-u+n);
				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, 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-v);
				else E2[u].pb(v-u+n);
				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, 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((i+j)%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: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: In function 'void encode3(vi&, int, int, int, int*, int*)':
encoder.cpp:168:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |   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++){
      |                ~^~~~~~~~~

Subtask #1
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5349 ms 13764 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4616 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 1541 ms 5896 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 1 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2273 ms 6852 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 2679 ms 6904 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3242 ms 7728 KB Output isn't correct
8 Correct 2881 ms 5608 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1534 ms 5656 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1495 ms 5660 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1652 ms 6168 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1857 ms 5408 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 2965 ms 7364 KB Output isn't correct
14 Correct 1908 ms 5616 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1898 ms 5672 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2251 ms 6936 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2251 ms 6756 KB Output isn't correct
18 Correct 2838 ms 7420 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 2524 ms 6756 KB Output isn't correct
20 Incorrect 2729 ms 7876 KB Output isn't correct
21 Incorrect 3135 ms 8332 KB Output isn't correct
22 Incorrect 3286 ms 7916 KB Output isn't correct
23 Incorrect 3248 ms 9104 KB Output isn't correct

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5349 ms 13764 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4616 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 1541 ms 5896 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 1 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2273 ms 6852 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 2679 ms 6904 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3242 ms 7728 KB Output isn't correct
8 Correct 2881 ms 5608 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1534 ms 5656 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1495 ms 5660 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1652 ms 6168 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1857 ms 5408 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 2965 ms 7364 KB Output isn't correct
14 Correct 1908 ms 5616 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1898 ms 5672 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2251 ms 6936 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2251 ms 6756 KB Output isn't correct
18 Correct 2838 ms 7420 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 2524 ms 6756 KB Output isn't correct
20 Incorrect 2729 ms 7876 KB Output isn't correct
21 Incorrect 3135 ms 8332 KB Output isn't correct
22 Incorrect 3286 ms 7916 KB Output isn't correct
23 Incorrect 3248 ms 9104 KB Output isn't correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5349 ms 13764 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4616 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 1541 ms 5896 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 1 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2273 ms 6852 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 2679 ms 6904 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3242 ms 7728 KB Output isn't correct
8 Correct 2881 ms 5608 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1534 ms 5656 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1495 ms 5660 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1652 ms 6168 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1857 ms 5408 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 2965 ms 7364 KB Output isn't correct
14 Correct 1908 ms 5616 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1898 ms 5672 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2251 ms 6936 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2251 ms 6756 KB Output isn't correct
18 Correct 2838 ms 7420 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 2524 ms 6756 KB Output isn't correct
20 Incorrect 2729 ms 7876 KB Output isn't correct
21 Incorrect 3135 ms 8332 KB Output isn't correct
22 Incorrect 3286 ms 7916 KB Output isn't correct
23 Incorrect 3248 ms 9104 KB Output isn't correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5349 ms 13764 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4616 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 1541 ms 5896 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 1 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2273 ms 6852 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 2679 ms 6904 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3242 ms 7728 KB Output isn't correct
8 Correct 2881 ms 5608 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1534 ms 5656 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1495 ms 5660 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1652 ms 6168 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1857 ms 5408 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 2965 ms 7364 KB Output isn't correct
14 Correct 1908 ms 5616 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1898 ms 5672 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2251 ms 6936 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2251 ms 6756 KB Output isn't correct
18 Correct 2838 ms 7420 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 2524 ms 6756 KB Output isn't correct
20 Incorrect 2729 ms 7876 KB Output isn't correct
21 Incorrect 3135 ms 8332 KB Output isn't correct
22 Incorrect 3286 ms 7916 KB Output isn't correct
23 Incorrect 3248 ms 9104 KB Output isn't correct