oj.uz

Submission #68028

# Submission time Handle Problem Language Result Execution time Memory
68028 2018-08-15T19:25:26 Z yusufake Permutation Recovery (info1cup17_permutation) C++
60 / 100
 4000 ms 22692 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 = 1e9 + 9; 
const int N   = 7e4 + 4; 
const int K = 288;

vector < pp > V[N];
unordered_map < ll , int > 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][ (t - L[j] + mod) % mod ]){
                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]++;
                for(j++; j<K; j++) f(L[j],t);    
                break;
            }
        y = x;
        
        /////
        if(i % K == 0){
            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 ]++;
            }
        }    
    }
    
    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: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 8 ms 5752 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 27 ms 6040 KB Output is correct
4 Correct 20 ms 6096 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 27 ms 6040 KB Output is correct
4 Correct 20 ms 6096 KB Output is correct
5 Correct 1739 ms 10784 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 27 ms 6040 KB Output is correct
4 Correct 20 ms 6096 KB Output is correct
5 Correct 1739 ms 10784 KB Output is correct
6 Execution timed out 4027 ms 22692 KB Time limit exceeded

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 27 ms 6040 KB Output is correct
4 Correct 20 ms 6096 KB Output is correct
5 Correct 1739 ms 10784 KB Output is correct
6 Execution timed out 4027 ms 22692 KB Time limit exceeded

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 27 ms 6040 KB Output is correct
4 Correct 20 ms 6096 KB Output is correct
5 Correct 1739 ms 10784 KB Output is correct
6 Execution timed out 4027 ms 22692 KB Time limit exceeded

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5752 KB Output is correct
2 Correct 15 ms 5988 KB Output is correct
3 Correct 27 ms 6040 KB Output is correct
4 Correct 20 ms 6096 KB Output is correct
5 Correct 1739 ms 10784 KB Output is correct
6 Execution timed out 4027 ms 22692 KB Time limit exceeded