oj.uz

Submission #68045

# Submission time Handle Problem Language Result Execution time Memory
68045 2018-08-15T19:47:54 Z yusufake Permutation Recovery (info1cup17_permutation) C++
100 / 100
 3979 ms 288672 KB 
#include<bits/stdc++.h> 
using namespace std; 

#define pb push_back
#define mp make_pair
#define st first
#define nd second

typedef long long ll; 
typedef pair < ll , ll > pp; 
const ll mod = 1610612745235283; 
const int N   = 7e4 + 4; 
const int K = 277;

vector < pp > V[N];
unordered_map < ll , bool > M[N];
pp T[N];

ll L[N],ans[N],n,u,i,j,k,x,y,t;
char s[N*10];

void f(ll &r, ll x) { r = (r + x + mod*3) % mod;  }

int main(){
    scanf("%lld",&n);
    V[0].pb( mp(0,0) ); M[0][0]=1;
    y = 0;
    for(i=1;i<=n;i++){
        scanf(" %s", s);
        u = strlen(s);
        x = 0;
        for(j=0;j<u;j++)
            x = (x*10LL + s[j]-'0') % mod;
        t = (x-y-1+mod*3) % mod;
        for(j=0;j<K;j++)
            if(M[j].find( (t - L[j] + mod) % mod ) != M[j].end() ){
                for(k=0;k<V[j].size();k++)
                    f(V[j][k].st , L[j]);
                L[j] = 0;
                for(k=0;k<V[j].size();k++)
                    if(V[j][k].st == t){
                        V[j].insert(V[j].begin() + ++k , mp(t,i));
                        break;
                    }                
                f(t,1);
                for(; k<V[j].size(); k++)
                    f(V[j][k].st,t);
                M[j].clear();
                for(auto x : V[j]) M[j][x.st] = 1;
                for(j++; j<K; j++) f(L[j],t);    
                break;
            }
        y = x;
        
        /////
        if(i>>10 != i+1>>10){
            t = 0;
            for(j=0;j<K;j++){
                for(auto x : V[j]){
                    T[++t] = mp(x.st+L[j],x.nd);
                    f(T[t].st,0);
                }
                V[j].clear();
                M[j].clear();
                L[j] = 0;
            }
            for(j=1;j<=t;j++){
                V[j>>8].pb(T[j]);
                M[j>>8][ T[j].st ] = 1;
            }
        }    
    }
    
    for(t=i=0;i<K;i++)
        for(auto x : V[i])
            ans[ x.nd ] = ++t;
    
    for(i=1;i<=n;i++)
        printf("%lld ",ans[i]-1);
    return 0;
}

Compilation message

permutation.cpp: In function 'int main()':
permutation.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(k=0;k<V[j].size();k++)
                         ~^~~~~~~~~~~~
permutation.cpp:40:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(k=0;k<V[j].size();k++)
                         ~^~~~~~~~~~~~
permutation.cpp:46:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(; k<V[j].size(); k++)
                       ~^~~~~~~~~~~~
permutation.cpp:56:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         if(i>>10 != i+1>>10){
                     ~^~
permutation.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
permutation.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", s);
         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 29 ms 6124 KB Output is correct
4 Correct 28 ms 6124 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 29 ms 6124 KB Output is correct
4 Correct 28 ms 6124 KB Output is correct
5 Correct 1599 ms 10196 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 29 ms 6124 KB Output is correct
4 Correct 28 ms 6124 KB Output is correct
5 Correct 1599 ms 10196 KB Output is correct
6 Correct 3461 ms 13572 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 29 ms 6124 KB Output is correct
4 Correct 28 ms 6124 KB Output is correct
5 Correct 1599 ms 10196 KB Output is correct
6 Correct 3461 ms 13572 KB Output is correct
7 Correct 2943 ms 13572 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 29 ms 6124 KB Output is correct
4 Correct 28 ms 6124 KB Output is correct
5 Correct 1599 ms 10196 KB Output is correct
6 Correct 3461 ms 13572 KB Output is correct
7 Correct 2943 ms 13572 KB Output is correct
8 Correct 2358 ms 96540 KB Output is correct
9 Correct 3979 ms 177280 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 29 ms 6124 KB Output is correct
4 Correct 28 ms 6124 KB Output is correct
5 Correct 1599 ms 10196 KB Output is correct
6 Correct 3461 ms 13572 KB Output is correct
7 Correct 2943 ms 13572 KB Output is correct
8 Correct 2358 ms 96540 KB Output is correct
9 Correct 3979 ms 177280 KB Output is correct
10 Correct 3839 ms 288672 KB Output is correct