oj.uz

답안 #67875

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67875 2018-08-15T11:35:27 Z osmanorhan Permutation Recovery (info1cup17_permutation) C++17
43 / 100
 4000 ms 3560 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#include <unordered_map>

#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset

using namespace std;

typedef long long Lint;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,char> ic;
typedef pair<db,db> dd;
typedef pair<int,ii> iii;
typedef pair<ii,ii> i4;

const int maxn = 70020;
const int maxk = 620;
const int MOd = 998244353;
const int K = 300;

int gs, a;
unordered_map<int,int> mp[maxk];
vector<ii> v[maxn];
int lazy[maxn];
int ans[maxn], ar[maxn];

int add( int a, int b ) {
	a += b;
	a %= MOd;
	if( a < 0 ) a += MOd;
	return a;
}

int mul( int x, int y ) {
	return (Lint)x*y % MOd;
}

bool ins( int g, int x, int &loc ) {
	//printf("asd %d -- %d\n",g,x);
	if( !mp[g].count( add( x, -lazy[g] ) ) ) return false;
	mp[g].clear();
	vector<ii> v2;
	int c = 0;
	int val = 0;
	for(int i=0;i<v[g].size();i++) {
		v[g][i].fi = add( v[g][i].fi, lazy[g] );
		
		if( c ) v[g][i].fi = add( v[g][i].fi, val );
		mp[g][ v[g][i].fi ] = 1;
		//printf("-- %d\n",v[g][i].fi);
		v2.pb( v[g][i] );

		if( v[g][i].fi == x ) { c = 1;
			val = add( x, 1 );
			int h = add( x, val );
			v2.pb( ii( h, loc ) );
			mp[g][h] = 1;

			//printf("-- %d\n",h);
		}
	}
	lazy[g] = 0;
	for(int i=g+1;i<gs;i++)
		lazy[i] = add( lazy[i], val );
	v[g] = v2;
	return true;
}

int main() {

    //freopen("asd.in","r",stdin);
    //freopen("output17.txt","w",stdout);
	gs = 1;
	scanf("%d",&a);
	ar[0] = 0;
	v[0].pb( ii( 0, 0 ) );
	mp[0][0] = 1;
	for(int i=1;i<=a;i++) {
		string s;
		cin >> s;
		int x = 0;
		for(int j=0;j<s.size();j++)
			x = add( mul( x, 10 ), s[j]-'0' );
		ar[i] = x;

		int c = 0;
		for(int j=0;j<gs;j++)
			if( ins( j, add(ar[i],-ar[i-1]-1), i ) ) { c = 1; break; }
		assert( c );
	}
	int cnt = -1;
	for(int i=0;i<gs;i++)
		for(int j=0;j<v[i].size();j++)
			ans[ v[i][j].se ] = ++cnt;

	for(int i=1;i<=a;i++) printf("%d ",ans[i]); printf("\n");


	return 0;
}

Compilation message

permutation.cpp: In function 'bool ins(int, int, int&)':
permutation.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[g].size();i++) {
              ~^~~~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<s.size();j++)
               ~^~~~~~~~~
permutation.cpp:116:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v[i].size();j++)
               ~^~~~~~~~~~~~
permutation.cpp:119:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=1;i<=a;i++) printf("%d ",ans[i]); printf("\n");
  ^~~
permutation.cpp:119:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int i=1;i<=a;i++) printf("%d ",ans[i]); printf("\n");
                                              ^~~~~~
permutation.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&a);
  ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2040 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2040 KB Output is correct
2 Correct 14 ms 2152 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2040 KB Output is correct
2 Correct 14 ms 2152 KB Output is correct
3 Correct 43 ms 2208 KB Output is correct
4 Correct 50 ms 2292 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2040 KB Output is correct
2 Correct 14 ms 2152 KB Output is correct
3 Correct 43 ms 2208 KB Output is correct
4 Correct 50 ms 2292 KB Output is correct
5 Execution timed out 4037 ms 3560 KB Time limit exceeded

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2040 KB Output is correct
2 Correct 14 ms 2152 KB Output is correct
3 Correct 43 ms 2208 KB Output is correct
4 Correct 50 ms 2292 KB Output is correct
5 Execution timed out 4037 ms 3560 KB Time limit exceeded

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2040 KB Output is correct
2 Correct 14 ms 2152 KB Output is correct
3 Correct 43 ms 2208 KB Output is correct
4 Correct 50 ms 2292 KB Output is correct
5 Execution timed out 4037 ms 3560 KB Time limit exceeded

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2040 KB Output is correct
2 Correct 14 ms 2152 KB Output is correct
3 Correct 43 ms 2208 KB Output is correct
4 Correct 50 ms 2292 KB Output is correct
5 Execution timed out 4037 ms 3560 KB Time limit exceeded

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2040 KB Output is correct
2 Correct 14 ms 2152 KB Output is correct
3 Correct 43 ms 2208 KB Output is correct
4 Correct 50 ms 2292 KB Output is correct
5 Execution timed out 4037 ms 3560 KB Time limit exceeded