oj.uz

답안 #830112

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
830112 2023-08-18T19:01:22 Z Antekb 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 1775 ms 12900 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];
	queue<int> spe;
	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());
		if(ile>=111){
			spe.push(v);
			spec[v]=1;
			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;
					}
				}
			}
			}
		}
	}
	for(int i=0; i<n; i++){
		if(!spec[i]){
			for(int u:E2[i]){
				assert(((u-i+n)%n)<512);
			}
		}
	}
	while(spe.size()){
		int v=spe.front();
		spe.pop();
		if(E2[v].size()>=111)continue;
		vi V;
		spec[v]=0;
		for(int u:E2[v]){
			if(2*(u-v)<=n)V.pb(u);
			else{
				E2[u].pb(v);
				if(E2[u].size()==111){
					spec[u]=1;
					spe.push(u);
				}
				if(!spec[u]){
					for(int i:E2[u]){
						assert(((i-u+n)%n)<512);
					}
				}
			}
		}
		E2[v]=V;
		
	}
	for(int i=0; i<n; i++){
		if(!spec[i]){
			for(int u:E2[i]){
				//assert(((u-i+n)%n)<512);
			}
		}
	}
	cerr<<sum<<"\n";
	for(int i=0; i<n; i++){
		sort(E2[i].begin(), E2[i].end());
		if(spec[i]){
			//assert(E2[i].size()>=111);
			nadaj(ans, 111, 7);
		}
		else{
			//assert(E2[i].size()<100);
			nadaj(ans, E2[i].size(), 7);
		}
		//assert(spec[i]==(E2[i].size()>=111));
		if(spec[i]){
			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]){
				//assert((u-i+n)%n<512);
				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(), 111), 7);
		if(E2[i].size()>=111){
			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>=111){
			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:174:12: warning: unused variable 'u' [-Wunused-variable]
  174 |    for(int u:E2[i]){
      |            ^
encoder.cpp: In function 'void encode3(vi&, int, int, int, int*, int*)':
encoder.cpp:228:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 |   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 1667 ms 12900 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 829 ms 5740 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
5 Incorrect 975 ms 6608 KB Output isn't correct
6 Incorrect 1172 ms 6704 KB Output isn't correct
7 Incorrect 1686 ms 7184 KB Output isn't correct
8 Correct 1289 ms 5468 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 890 ms 5480 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 917 ms 5496 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1008 ms 6004 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1035 ms 5268 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1730 ms 6988 KB Output isn't correct
14 Correct 1066 ms 5448 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1083 ms 5580 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1131 ms 6476 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1115 ms 6372 KB Output isn't correct
18 Incorrect 1244 ms 6876 KB Output isn't correct
19 Incorrect 1422 ms 6256 KB Output isn't correct
20 Correct 1226 ms 7428 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1305 ms 7676 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1775 ms 7152 KB Output isn't correct
23 Correct 1371 ms 7952 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1667 ms 12900 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 829 ms 5740 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
5 Incorrect 975 ms 6608 KB Output isn't correct
6 Incorrect 1172 ms 6704 KB Output isn't correct
7 Incorrect 1686 ms 7184 KB Output isn't correct
8 Correct 1289 ms 5468 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 890 ms 5480 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 917 ms 5496 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1008 ms 6004 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1035 ms 5268 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1730 ms 6988 KB Output isn't correct
14 Correct 1066 ms 5448 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1083 ms 5580 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1131 ms 6476 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1115 ms 6372 KB Output isn't correct
18 Incorrect 1244 ms 6876 KB Output isn't correct
19 Incorrect 1422 ms 6256 KB Output isn't correct
20 Correct 1226 ms 7428 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1305 ms 7676 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1775 ms 7152 KB Output isn't correct
23 Correct 1371 ms 7952 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1667 ms 12900 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 829 ms 5740 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
5 Incorrect 975 ms 6608 KB Output isn't correct
6 Incorrect 1172 ms 6704 KB Output isn't correct
7 Incorrect 1686 ms 7184 KB Output isn't correct
8 Correct 1289 ms 5468 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 890 ms 5480 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 917 ms 5496 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1008 ms 6004 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1035 ms 5268 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1730 ms 6988 KB Output isn't correct
14 Correct 1066 ms 5448 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1083 ms 5580 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1131 ms 6476 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1115 ms 6372 KB Output isn't correct
18 Incorrect 1244 ms 6876 KB Output isn't correct
19 Incorrect 1422 ms 6256 KB Output isn't correct
20 Correct 1226 ms 7428 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1305 ms 7676 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1775 ms 7152 KB Output isn't correct
23 Correct 1371 ms 7952 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1667 ms 12900 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 829 ms 5740 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 73 call(s) of encode_bit()
5 Incorrect 975 ms 6608 KB Output isn't correct
6 Incorrect 1172 ms 6704 KB Output isn't correct
7 Incorrect 1686 ms 7184 KB Output isn't correct
8 Correct 1289 ms 5468 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 890 ms 5480 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 917 ms 5496 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1008 ms 6004 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 1035 ms 5268 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1730 ms 6988 KB Output isn't correct
14 Correct 1066 ms 5448 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1083 ms 5580 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1131 ms 6476 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1115 ms 6372 KB Output isn't correct
18 Incorrect 1244 ms 6876 KB Output isn't correct
19 Incorrect 1422 ms 6256 KB Output isn't correct
20 Correct 1226 ms 7428 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1305 ms 7676 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1775 ms 7152 KB Output isn't correct
23 Correct 1371 ms 7952 KB Output is correct - 60188 call(s) of encode_bit()